The Periodical Vehicle Routing Problem: Research Overview and Practical Application to a South German Fast Food Restaurant

Table of Contents

Abbreviations

List of Figures

List of Tables

Symbols

1 Introduction

2 The Vehicle Routing Problem (VRP)
2.1 The basic developments of the Vehicle Routing Problem
2.1.1 The Bin Packing Problem (BPP)
2.1.2 The Traveling Salesman Problem (TSP)
2.2 The Vehicle Routing Problem (VRP)
2.2.1 The mathematical formulation of the Vehicle Routing Problem
2.2.2 Different kinds of the Vehicle Routing Problem

3 The periodic(al) vehicle routing problem (PVRP)
3.1 The classical PVRP
3.2 Pioneer Work for the PVRP
3.2.1 The concept of Beltrami and Bodin
3.2.2 The concept of Russel and Igo
3.3 Additional work in the 1980s and 1990s
3.3.1 The concept of Christofides and Beasley
3.3.2 The concept of Russel and Gribbin
3.3.3 The concept of Chao, Golden, and Wasil
3.3.4 The concept of Cordeau, Gendreau, and Laporte
3.4 Applied research of today
3.4.1 The concept of Shih and Chang
3.4.2 The concept of Angelelli and Speranza
3.4.3 The concept of Blakeley and Knolmajer
3.4.4 The concept of Alegre, Laguna, and Pacheco

4 The fast food industry and its reasons of success
4.1 McDonald’s
4.1.1 The beginning of McDonald’s
4.1.2 The expansion of McDonald’s
4.2 Burger King
4.2.1 Historical facts
4.2.2 The expansion of Burger King
4.3 Subway
4.3.1 The beginning
4.3.2 The expansion and the principles of shock frosting
4.3.3 The health factor and the German challenge

5 The virtual fast-food chain and the Optimization Programming Language (OPL)
5.1 The virtual fast-food chain
5.1.1 The locations of the virtual fast-food chain
5.1.2 Distances, the resulting fuel costs, and the travel time
5.2 Inventory Costs
5.3 Trucks and driving costs
5.3.1 Trucks
5.3.2 Trucker’s loans
5.4 Opening hours
5.4.1 Different categories of the restaurants
5.4.2 Attendance
5.5 Demand of the restaurants
5.5.1 Range of products
5.5.2 Total delivery quantity
5.6 The Optimization Programming Language (OPL)
5.6.1 The development of the Optimization Programming Language

6 The creation of the mathematical model for the virtual fast-food chain
6.1 Symbols needed for the creation of the mathematical model
6.2 Objective function
6.3 Side conditions

7 Sensitivity analysis
7.1 Basic results
7.2 ILOG’s limit in memory capacity
7.3 Various examples
7.3.1 Five locations, five trucks, and 28 days - normal
7.3.2 Five locations, five trucks, and 28 days – changed demand
7.3.3 Five locations, five trucks, and 28 days – different travel time
7.3.4 Five locations, five trucks, and 28 days – low capacity and different travel time
7.3.5 Five locations, five trucks, and 28 days – changed inventory costs
7.3.6 Five locations, five trucks, and 28 days – changed frequency
7.4 Five locations, five trucks, and 28 days – comparison

8 Conclusion and a perspective of the PVRP in the future

Appendix

Bibliography

Laws and Directives

Abbreviations

illustration not visible in this excerpt

List of Figures

Figure 2-1: The 2-D bin packing problem (BPP)

Figure 2-2: TSP

Figure 3-1: initial (left) and modified (right) routing procedure

Figure 3-2: PVRP with an intermediate facility

Figure 3-3: initial route and route after CROSS interchange

Figure 5-1: the locations of the virtual fast-food chain

Figure 5-2: average attendance per hour (part 1)

Figure 7-1: screenshot no solution

Figure 7-2: screenshot First reduced calculation

Figure 7-3: screenshot abortion

Figure 7-4: screenshot changed demand

Figure 7-5: screenshot different travel time

Figure 0-1: Consume restraint in Germany

Figure 0-2: press info (February 7, 2005) GfK’s European Consumer Study 2004, Nuremberg

Figure 0-3: Gastronomy in Germany: development of the attendance during Winter 2003/ 2004 (in percent)

Figure 0-4: Subway Restaurants in the Munich area

Figure 0-5: depot (0) and restaurant (1)

Figure 0-6: restaurant (2) and restaurant (3)

Figure 0-7: restaurant (4) and restaurant (5)

Figure 0-8: restaurant (6) and restaurant (7)

Figure 0-9: restaurant (8) and restaurant (9)

Figure 0-10: restaurant (10) and restaurant (11)

Figure 0-11: restaurant (12) and restaurant (13)

Figure 0-12: restaurant (14) and restaurant (15)

Figure 0-13: restaurant (16) and restaurant (17)

Figure 0-14: restaurant (18) and restaurant (19)

Figure 0-15: restaurant (20) and restaurant (21)

Figure 0-16: restaurant (22) and restaurant (23)

Figure 0-17: restaurant (24) and restaurant (25)

Figure 0-18: distances between the depot and each retailer (part 1)

Figure 0-19: distances between the depot and each retailer (part 2)

Figure 0-20 : fuel costs between the depot and each retailer (part 1)

Figure 0-21: fuel costs between the depot and each retailer (part 2)

Figure 0-22: official opening hours

Figure 0-23: adapted opening hours

Figure 0-24: attendance per day (morning)

Figure 0-25: attendance per day (lunch and afternoon)

Figure 0-26: attendance per day (dinner)

Figure 0-27: attendance per day (night).

Figure 0-28: demand – each product - yellow category (part 1)

Figure 0-29: demand – each product - yellow category (part 2)

Figure 0-30: demand – each component - yellow category (part 1)

Figure 0-31: demand – each component - yellow category (part 2)

Figure 0-32: demand – each component - yellow category (part 3)

Figure 0-33: demand – each product – green category (part 1)

Figure 0-34: demand – each product – green category (part 2)

Figure 0-35: demand – each product – green category (part 3)

Figure 0-36: demand – each component - green category (part 1)

Figure 0-37: demand – each component - green category (part 2)

Figure 0-38: demand – each component - green category (part 3)

Figure 0-39: demand – each product - brown category (part 1)

Figure 0-40: demand – each product - brown category (part 2)

Figure 0-41: demand – each component - brown category (part 1)

Figure 0-42: demand - each component - brown category (part 2)

Figure 0-43: demand - each component - brown category (part 3)

Figure 0-44: weekly demand - each component - all categories (part 1)

Figure 0-45: weekly demand - each component - all categories (part 2)

Figure 0-46: weekly demand - each component - all categories (part 3)

Figure 0-47: inventory after one week - each component - all categories (part 1)

Figure 0-48: inventory after one week - each component - all categories (part 2)

Figure 0-49: inventory after one week - each component - all categories (part 3)

Figure 0-50: inventory after one week - each component - all categories (part 4)

Figure 0-51: implementation in ILOG (normal)

Figure 0-52: implementation in ILOG (changed demand)

Figure 0-53: implementation in ILOG (different travel time)

Figure 0-54: implementation in ILOG (low capacity and different travel time)..

Figure 0-55: implementation in ILOG (changed inventory costs)

Figure 0-56: implementation in ILOG (changed frequency)

List of Tables

Table 3-1: PVRP with four days

Table 5-1: totaling attendance per meal

Table 5-2: average attendance per hour (part 2)

Table 7-1: frequencies

Symbols

illustration not visible in this excerpt

1 Introduction

In the middle of May 1997 Gerd Raupeter, CEO of McDonald’s Deutschland Inc. (Mc Donald’s Germany Inc.), had to announce that some restaurants were sold out of shrimps^[1]. The keen customer’s demand for this kind of seafood already exceeded the expected forecasts one week after starting the ongoing “Fisch-Wochen” (fish-weeks) mission. As these circumstances highlighted an accurate product choice for the fast food corporation Mr. Raupeter has nevertheless been pleased about it.

Otherwise, such an awkward situation could be prevented by developing a demand-driven scheduling for each restaurant in the future. The Periodic(al) Vehicle Routing Problem (PVRP) seems to be a tailor-made solution for the reason that exact planning has to be done and “…delivery routes must be constructed over a period of time (for example, multiple days).”^[2]

Observations and analyzes in the literature in most of the industries deal with a constant demand for goods and with only one good. Moreover the one-of-a-kind client prevails. But for the application of the PVRP to the gastronomy there are some exceptions to be considered.

As this paper presents a solution approach of the delivery problem for the fast-food industry in South Germany, there are products to be transported consisting of diverse components. Although there are nearly identical opening hours, the eating places – the clientele to be delivered - due to their irregular demand for food and beverages are varying from the unique purchaser. Another singularity lies in the conformity of the foodstuff which is reflected in the comparability of each restaurant. Therefore the enduring solution approach will be done in a sample of some fast food restaurants.

This paper herein is organized as follows. In the second and third chapter, various theories that could lead depots how to organize its delivery are reviewed, with an emphasis on the Vehicle Routing Problem (VRP) as well as the PVRP.

The success of the fast-food industry starting in the 1950s in the U.S. is presented in Chapter 4. Furthermore, this section highlights the implications of McDonald’s, Burger King, and Subway for the changing appetite of the USA as well as the whole world.

Chapter 5 looks at the different aspects of the virtual fast-food retailer in South Germany with an extent to the description of the Optimization Programming Language (OPL) including ILOG.

The vendor’s mathematical problem formulation is presented in Chapter 6. In the subsequent chapter possible solution approaches by the application of ILOG are given, followed by an examination of the results. The variables of some restaurants differ a little bit therein in order to compare these achievements with each other one.

Chapter 8 summarizes, concludes and attempts to forecast the possible development of the PVRP-technique for the future.

2 The Vehicle Routing Problem (VRP)

Based on the calculations of the German Federal Ministry of Transport, Building and Housing in 2000, freight transportation will rise of 78.8% during the following years^[3]. In order to prevent the trucks from getting into the resulting traffic jams and to minimize the transportation costs, this situation reflects the need for an improved transport scheduling. Furthermore, every virtual fast-food restaurant, used in this thesis, expects food delivered in time. This transport situation can be related to the problem of designing a set of routes to supply customers by vehicles from a central facility or depot, called the Vehicle Routing Problem (VRP)^[4].

2.1 The basic developments of the Vehicle Routing Problem

Given the fact that the VRP whose goal is to minimize the cost of distribution “… can be seen as a merge of two well-known problems: the Traveling Salesperson (TSP) and the Bin Packing Problem (BPP)…”^[5], this paper describes these two solution approaches first.

2.1.1 The Bin Packing Problem (BPP)

The Bin Packing Problem (BPP) consists of packing a list L = (a1, …, an) of items of sizes sj (s1, …, sn) into a supply of bins of a certain capacity, say B. Its objective is to assign each item of the list L to one bin so that its total capacity does not exceed B. Besides, the number of bins that contain a given set of weights, dependent on a limitation of the total weight each bin can contain has to be minimized^[6]. This packing problem is called the one-dimensional (1-D) Bin Packing Problem if the sizes sj are fixed. “Many potential applications, such as packing small information packets into somewhat larger fixed-size ones, involve integer item sizes, fixed and relatively small values of B, and large values of n.“^[7]

The figure below displays the two dimensional (2-D) Bin Packing Problem whose ambition is to pack different sized objects (as marked as a1, …, a6 ) of various weights (as marked from s1, …, s6) into a specific amount of boxes n (herein n = 2, box 1 and box 2) so that the totaling weight of articles in each box is equal to or less than 25 kg (as marked as capacity B), subject to a limitation of using as few of the bins as possible^[8]. Furthermore, there are no constraints on grouping or diversity, but the packed items are not free to overlap.

illustration not visible in this excerpt

Figure ‎ 2 - 1 : The 2-D bin packing problem (BPP)

By associating the 0-1 variable^[9] (constraint 1.3), the mathematical formulation of the problem is as follows^[10]:

Minimize illustration not visible in this excerpt

such that[illustration not visible in this excerpt]

illustration not visible in this excerpt (1.3)

where illustration not visible in this excerpt illustration not visible in this excerpt

Beyond, there is the three dimensional (3-D) Bin Packing Problem. The orthogonal 3-D bin’s volume has to be minimized by packing dimensional boxes into it^[11]. Furthermore, as Karp^[12] denoted the BPP as NP-complete^[13], no general method of solution is known. Furthermore, Johnson^[14], Papadimitriou and Steiglitz^[15], Parker and Rardin^[16], Leung^[17], Ramanan^[18], or Hall et al.^[19] have suggested some heuristic^[20] procedures for variants of the BPP.

Since the goal of this thesis is to reduce the transport costs instead of reducing the number of packed bins the different types of the Bin Packing Problem described in this subchapter are just providing a basis for the development of a transport scheduling for the virtual fast-food retailer of this paper.

2.1.2 The Traveling Salesman Problem (TSP)

While the BPP tries to find the minimum number of bins filled with a set of items, the Traveling Salesman Problem (TSP) is looking for the most efficient (i.e., least total costs) Hamiltonian cycle^[21] a salesman can take through each of n cities^[22]. As shown in the figure below, a salesperson starting in city 0 has to visit six cities (1 through 6) once and has to come back to the starting point. A possible route is represented by Figure 2-2 (the route on the left side: 0→ 2 → 4 → 5 → 3 → 1 → 0) with its total length of 144 km. This selection does not demonstrate the best solution because the route on the right side in the same figure reduces the total distance to 99 km (0→ 2 → 5 → 3 → 4 → 1 → 0). Assuming that each city can be joined by a link, the total number of potential routes through n (or six as in the two figure below) cities is ½ n! (or 360 as in the figure below).

illustration not visible in this excerpt

illustration not visible in this excerpt

Figure ‎ 2 - 2 : TSP

The most challenging variations of the TSP are the symmetric TSP^[23] and the asymmetric TSP^[24], both of them analyzed by Lenstra^[25] e.g., as well as the Euclidean TSP^[26] denoted by Papadimitriou^[27] e.g. Additionally, each kind of TSP is NP-complete^[28]. Given the fact that the Traveling Salesman Problem is, as described above, just a part of the VRP, this paper will not specify the mathematical formulation of the TSP illustrated by Rardin^[29].

2.2 The Vehicle Routing Problem (VRP)

As shown above^[30], the vehicle routing problem (VRP) is a combination of the TSP and the BPP. It was introduced by Dantzig and Ramser^[31] in 1959 as a generalization of the TSP.

In this graph-based problem, the quantity di of a single commodity has to be delivered by a fleet of k vehicles from a central depot {0} to i illustration not visible in this excerpt N = {1, …, n} customers. Each vehicle is of identical capacity C, leaves typically the depot with a full or nearly full load and returns empty. The costs of delivery cij from city i to city j, for 0 ≤ i; j ≤ n, are symmetric meaning the transport costs from city i to city j are the same as the transport costs from city j to city i (cij = cji). As a consequence, the freight costs from city i to city i are zero (cii = 0) and they are not depending on the quantity loaded in the vehicles.

Domschke^[32] views the customers (as marked as {1, …, 5}) and the depot (as marked as {0}) as the nodes of each graph. Cij = l marks the costs of the route of the length xe between node i and node j. (e.g. c13 = 12 denotes the costs of the route of the length xe between node 1 and node 3. Further costs are not marked herein^[33] ). The objective of this problem is to minimize the total costs of a route serviced by one of the k vehicles so that all customers are served, and the total distance traveled by the fleet has to be reduced to its minimum.

2.2.1 The mathematical formulation of the Vehicle Routing Problem

By associating a 0-1 variable [constraint (2.5)] with each edge e illustration not visible in this excerptE in the graph, the mathematical formulation of the Vehicle Routing Problem whose roots were denoted by Laporte and Desrochers^[34] is as follows^[35]:

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

This complex combinatorial optimization problem also includes “… illustration not visible in this excerpt, an obvious lower bound on the number of vehicles needed to service the customers in set T.”^[36] While constraint (2.1) reduces the number of vehicles to exactly k, constraint (2.2) ensures that one delivery combination is chosen for each client. Constraint (2.3) is present to ensure that capacity C will not be exceeded during any route.

Furthermore it ensures that the depot is included. Given the fact that the BPP and the TSP, the basis for the VRP, have already been described as NP-hard^[37], Garey and Johnson^[38], Lenstra and Rinnooy Kan^[39] as well as Dror and Trudeau^[40] denoted the VRP as an NP-hard problem. In addition, VRP is an extremely multifaceted problem.

2.2.2 Different kinds of the Vehicle Routing Problem

Although Ralphs, Pulleyblank, and Trotter^[41] blinded out the idea of the BPP so as to solve the VRP, this thesis includes this idea. Besides, as a part of the Operations Research (OR)^[42] area whose success is based on the development of computer systems, the VRP emerged in the 1960s, and has been studied by Christofides and Eilon^[43], Yellow^[44], Wren and Holliday^[45],

Gillett and Miller^[46], Christofides, Mingozzi, and Toth^[47], or Ho and Haugland^[48].

Reimann, Doerner, and Hartl^[49] even enhanced the performance of the VRP in terms of computational effort by using an algorithm based on the Savings based Ant System. The fact that VRP’s planning period is just a single day has prompted the development of different kinds of variations: Toth and Vigo^[50] give a review of the heuristic and the exact methods of the Capacitated VRP (CVRP), a VRP serving less than 50 customers and with the additional constraint that each vehicle is of homogeneous capacity and transports a single commodity.

Another important extension of the CVRP is the Vehicle Routing Problem with Time Windows (VRPTW). The “…service at each customer must start within an associated time window and the vehicle must remain at the customer location during service.”^[51] Additional main variants of the VRP are the VRP with Backhauls studied by Toth and Vigo^[52] and the VRP with Pickup and Delivery examined by Desaulniers et al^[53].

Since the virtual fast-food chain used in this thesis does not need a delivery every day, the VRP which is reduced to a single-day is not appropriate. The Periodic(al) Vehicle Routing Problem (PVRP), a further generalization of the VRP extends the time horizon to a period of days seems. Its basic idea is discussed in the following chapter.

3 The periodic(al) vehicle routing problem (PVRP)

As denoted in the chapter above, the Periodic(al) Vehicle Routing Problem (PVRP) is another extension of the VRP. It generalizes the classical problem by enlarging the daily planning period to a set of t days (illustration not visible in this excerpt). If T = 1, “…then PVRP becomes an instance of the classical VRP.”^[54]

After having proposed heuristics applied to waste collection problems, Beltrami and Bodin^[55] pioneered the PVRP concept in the 1970s. Further pioneers were Russell and Igo^[56] who described the decisions to be performed by using the term assignment problem (see for both of them chapter 3.2). Christofides and Beasley^[57] published an interchange heuristic method in 1984 (see chapter 3.3.1). Additional work was studied by Tan and Beasley^[58] using the heuristics of Fisher and Jaikumar^[59] in 1984. This research is not specified herein. A four-phase approach to the PVRP was developed by Russell and Gribbin^[60] in 1991 (see chapter 3.3.2). Based on the concept of “record-to-record travel (RRT)”^[61] developed by Dueck^[62] Chao, Golden, and Wasil^[63] built a heuristic applied to problems from the literature (see chapter 3.3.3). Cordeau, Gendreau, and Laporte^[64] presented a Tabu Search Metaheuristic to solve the VRP, the PVRP, the Periodic Traveling Salesman Problem (PTSP), and the Multi-Depot Vehicle Routing Problem (MDVRP) in 1995 (see chapter 3.3.4). In 1998, Hadjiconstantinou and Baldacci^[65] even extended the Periodic(al) Vehicle Routing Problem when they were doing research with multiple depots. In 2001, Drummond, Ochi, and Vianna^[66] presented an asynchronous parallel metaheuristic for the Periodic(al) Vehicle Routing Problem. Both of these research findings are not applied to this thesis.

In the course of 2001, Shih and Chang^[67] readopted the idea of waste treating and combined a standard VRP and a mixed integer programming method in order to get an algorithm for period routing for infectious waste in Taiwan (see chapter 3.4.1). One year later, Angelelli and Speranza^[68] extended the waste collection concept by the possibility of reloading the vehicles during a delivery-day-combination (see chapter 3.4.2). Blakeley and Knolmajer^[69] adapted the PVRP for Schindler’s maintenance operations in 2003 (see chapter 3.4.3). Moreover, Alegre et al.^[70] optimized the pick-up of raw materials for Bentzeler, a manufacturer of auto parts, with FortMp^[71] in 2004 (see chapter 3.4.4).

3.1 The classical PVRP

In the classical Periodic(al) Vehicle Routing Problem, a graph-based problem, the quantity di of a set of products must be delivered by a fleet of k vehicles from a central depot {0} to a group of i illustration not visible in this excerpt N = {1, …, n} retailers. The truck drivers typically leave the depot with a full or nearly full load and return empty within a day. Each client has to be visited at least once or several f times, as he requires, over a period T, where 1 ≤ f ≤ T. But according to the theory of the VRP the clientele can be supplied with goods only once a day by one vehicle. Additionally, the time constraint, when a client wants to be visited, has to be considered. This means that the planning of a day-combination and the designing of feasible routes has to be done at the same time. In the classical PVRP, each vehicle is of identical capacity C and each purchaser has a known daily demand of products di. Besides, the costs of delivery cij from city i to city j, for 0 ≤ i; j ≤ n, are symmetric.

The aim of the PVRP is to assign customer’s visits to vehicle routes on a special day t^[72] in order to minimize the distribution costs during the period without displeasing the side constraints as the fixed capacity of the vehicles e.g. As Vianna, Ochi, and Drummond^[73] have already denoted, the first step is to generate feasible combinations for each consumer. For example, possible combinations of a time period M consisting of four days {t = 1, t = 2, t = 3, and t = 4} are illustrated in Table ‎ 3-1 (0 means no delivery on this day; q signifies a delivery on this day).

illustration not visible in this excerpt

Table ‎ 3 - 1 : PVRP with four days

If three visits during the period are required, then the following feasible alternatives are: {t = 2, t = 3, and t = 4}, {t = 1, t = 3, and t = 4}, {t = 1, t = 2, and t = 4}, and {t = 1, t = 2, and t = 3}, (or the options: 12, 13, 14, and 15). After the finding of all possible combinations, one of them has to be selected on condition that all constraints, described above, are satisfied and that the distribution costs are minimized. As Mingozzi and Valletta^[74] affirmed during Odysseus 2003^[75] there is no exact method to solve the NP-hard PVRP. As a result, it cannot be solved to optimality within reasonable time (for problems of practical size).

3.2 Pioneer Work for the PVRP

While the previous subchapter has described the basic idea of the PVRP concept including the different kinds of constraints to be considered, this section gives an overview of the first basic research studies beginning in the early 1970s. It highlights the pioneer concept of Beltrami

and Bodin^[76] of 1974 as well as the algorithm of Russel and Igo^[77] of 1979.

3.2.1 The concept of Beltrami and Bodin

In 1974, Beltrami and Bodin faced the problem of how to organize the waste collection home by home for New York’s Environmental Protection Agency concerning the vehicle fleet, the amount of the labor force, and the feasible location of the factory equipment. Discovering the connection between them, they pioneered the PVRP concept by enhancing the Chinese Postman Problem^[78] using additional vehicles.

First, the above described constraints of delivering an amount of goods from a depot to their customers are somewhat modified. A new symmetric graph-based scheduling is generated.

illustration not visible in this excerpt

Figure ‎ 3 - 1 : initial (left) and modified (right) routing procedure^[79]

The defiance is now to collect waste from different sites and to transport it to the garbage dumps afterwards. Concerning the fact that the amount to be collected is dissimilar in each plant served three or six times per week poses another challenge.

In order to find a solution for the appearing complex problem, Beltrami and Bodin modify the Clarke and Wright algorithm^[80]. This one is combined with randomized search procedures. Consequently, the results of the adjustments are denoted in different figures as in shown in Figure 3-1.

Afterwards, the daily routes are assigned to the fleet of vehicles the way it is described in the instruction section of the PVRP^[81]. When a randomized chosen route does not achieve time savings in comparison with another one, this route combination will be eliminated. This method allows obtaining better results “…when the demand on many of the nodes is near the capacity of the vehicle.”^[82] Furthermore, there is the routing of the street sweepers including the making of subgraphs and an Euler tour^[83] to be created. In view of the fact that this scheduling is distinguishable from the requested route-planning for the fast-food chain, this paper does not particularize this problem.

Above and beyond, given that the aim of the concept of Beltrami and Bodin is to minimize the time to be traveled and to select the feasible amount of vehicles to be used instead of minimizing the costs of distribution, as requested for the PVRP of the virtual fast-food retailer illustrated in this paper, further statements of Beltrami and Bodin are not issued herein.

3.2.2 The concept of Russel and Igo

In what follows the pioneer concept of Russel and Igo who developed an algorithm for “… assigning points to days of the week in order to minimize weekly travel distance (time)…”^[84] is described.

In addition, the capacity constraints and the servicing of each point by one vehicle have to be considered. As it can be seen, their idea is similar to the concept of Beltrami and Bodin. But the model presented herein is expanded to more than 750 points clustered if equal. Nevertheless, the theory of creating node-based figures^[85] is applied to their applied research with the exception that the randomized search procedures are replaced by heuristics. Instead of only using the Clark and Wright algorithm having confirmed the best cost effectiveness during their studies the MTOUR^[86] algorithm having illustrated the most precise freedom from error is used as well.

The results show the data dependence of the points representing all the more points there are the more feasible it is to build several depots. Additionally, the more far-flung the demand points of the customers are the more difficult it is to find an appropriate solution for the location of the repository.

3.3 Additional work in the 1980s and 1990s

While Beltrami and Bodin as well as Russel and Igo developed basic work for solving the periodic vehicle routing problem, the following years mark the development of further applied economic research. On this account this section emphasizes the waste collection of Christofides and Beasley^[87], the four-phase approach to the PVRP by Russel and Gribbin^[88], the amount of different solution techniques by Chao, Golden, and Wasil^[89], and the heuristic by Cordeau, Gendreau, and Laporte^[90].

3.3.1 The concept of Christofides and Beasley

As mentioned further above, there is no exact method to solve the NP-hard PVRP. But Christofides and Beasley wanted “…to give an exact formulation of the PVRP...”^[91] although they developed an interchange heuristic.

In order to get a better understanding of the conceptual formulation of the classical PVRP, the notations used in chapter 3.1 are applied to the model of Christofides and Beasley^[92], similar to the formulation of Golden, Magnanti, and Nguyen^[93]:

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

As it can be seen in this mathematical formulation of the PVRP, the aim is to minimize the costs of distribution (3.1). The constraints (3.2), (3.3), and (3.6) are fulfilling the delivery combination requests satisfying the right amount to be delivered to the right customers and the feasible time pattern when to be delivered. The feasible use of vehicles concerning their scheduling (3.4), their capacity (3.10), and the time planning (3.9) is also ensured. Furthermore, the vehicles can only drive once a day (3.8), and after having delivered goods they must leave the clientele (3.5). Therefore, Christofides and Beasley split the PVRP into several VRPs each one representing one day.

In order to solve the set up equation, each VRP is transformed to a median subproblem or to a TSP subproblem. Both of them are represented by equation (3.7) as the set of subtour elimination constraints. New algorithms are created according to the definition of the PVRP. They include an assignment combination and an interchange heuristic.

As a result, the outcomes are evidence for the fact that the algorithm for the traveling salesman subproblem presents a more enhanced and a cheaper solution to the problem than the median problem.

3.3.2 The concept of Russel and Gribbin

Despite the fact that Christofides and Beasley developed an extended mathematical version of the PVRP with a lot of constraints, Russell and Gribbin^[94] shortened the PVRP model denoted in the following:

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

The notations used in the subchapters above have been applied to the model presented herein. Furthermore, A denotes the set of arcs in the network, N1 denotes the set of n customers nodes, and N2 denotes the set of nodes representing delivery combinations. As it can be seen, the assignment function (4.2), the time constraint (4.3), as well as the capacity constraint (4.4) still exist. (4.5) and (4.6) guarantee an “…upper bound of 1 on each of the flows out of the delivery combination transshipment nodes.”^[95] In order to be able to minimize the costs of distribution (4.1), Russell and Gribbin bring Fisher and Jaikumar’s algorithm^[96] into play. Besides, Tan and Beasley, whose research is not considered in this paper, used the formulation of Fisher and Jaikumar in 1984. After having examined some problems from literature, Russell and Gribbin find out that this algorithm is best appropriate for a single-day VRP.

Its application on a PVRP needs an extension^[97] making the problem more intricate. First, a seed point v is chosen for each day t of the period. Afterward, the customers are assigned to the routes {depot, client i, v} by calculating the additional time to travel and the consequentially supplementary costs of insertion as extra costs illustration not visible in this excerpt illustration not visible in this excerpt. Ten test problems, also from the literature^[98], are analyzed using this algorithm. They confirm an improved solution method. Further enhancements are made by a PTSP heuristic, a modified interchange heuristic, and a 0-1 tour improvement model.

[...]

---

^[1] cf. Salz, J. and Bauman, M., 1997: Neue Rezepte, p. 63

^[2] cf. Francis, P. et al., 2004: The period vehicle routing problem with service choice, p. 1

^[3] The rise of 78.8% represents an increase from 236 billion tonne-kilometers in 2000 to 422 billion tonne-kilometers by 2015 on the streets., cf. German Federal Ministry and Transport, Building and Housing, 2000: Verkehrsbericht 2000 – Kurzfassung, p. 6

^[4] cf. Christofides N. and Beasley, J.E. (1984): The Period Routing Problem, p. 237

^[5] cf. Pereira, F.B. et al., 2002: GVR: a New Genetic Representation for the Vehicle Routing Problem, p. 95

^[6] cf. Kao, C.-Y., 1992: A Stochastic Approach for The One-Dimensional Bin-Packing Problems

^[7] cf. Csirik, J. et al., 2002: On the Sum-of-Squares Algorithm for Bin Packing, p. 208

^[8] cf. Smith, D., 1985: Bin Packing With Adaptive Search

^[9] 0-1 or binary variables are limited to values 0 and 1, cf. Rardin, R., 1998: Optimization in Operations Research, p. 53

^[10] cf. Anis, M. et al., 2002: Dynamic and Leakage Power Reduction in MTCMOS Circuits Using an Automated Efficient Gate Clustering Technique, p. 483

^[11] Possible applications could be found in stock cutting examples of rectangular glass e.g., cf: Lin, J.-L. et al., 1993: Hybrid Genetic Algorithm for Container Packing in Three Dimensions

^[12] cf. Karp, R., 1972: Reducibility among combinatorial problems, pp. 85-104.

^[13] A decision problem C “… is said to be NP-complete if all problems in NP can be polynomially reduced to ...” it, cf. Wolsey L.A., Nemhauser, G.L., 1988: Integer and Combinatorial Optimization, p. 132, “"Reducible" here means that for every problem L, there is a polynomial-time many-one reduction, a deterministic algorithm which transforms instances l ∈ L into instances c ∈ C, such that the answer to c is YES if and only if the answer to l is YES.”, cf. Wikipedia, the free encyclopedia, 2005: NP-complete

^[14] cf. Johnson, D. S., 1974: Fast algorithms for bin- packing

^[15] cf. Papadimitriou, C.H. and Steiglitz, K., 1982: Combinatorial Optimization: Algorithms and Complexity

^[16] cf. Parker, R.G. and Rardin, R.L., 1988: Discrete Optimization

^[17] cf. Leung, J.Y.-T., 1989: Bin packing with restricted piece sizes

^[18] cf. Ramanan, P., 1989: Average-case analysis of the smart next fit algorithm

^[19] cf. Hall, N.G. et al., 1998: Bin packing problems in one dimension: heuristic solutions and confidence intervals

^[20] Krone described the meaning of heuristic in: Krone, M.J., 1970: Heuristic Programming Applied to Scheduling Problems

^[21] “Hamiltonian circuit, also called a Hamiltonian cycle, Hamilton circuit, or Hamilton cycle, is a graph cycle (i.e., closed loop) through a graph that visits each node exactly once”, cf. Skiena, S., 1990: “Hamiltonian Cycles.”, p. 196)

^[22] cf. Pack, L., 1991: Das Traveling-Salesman-Problem und seine heuristische Lösung durch paarweisen Ortstausch, p. 1

^[23] The distance or cost of passing from A to B is equal to the distance or cost of passing from B to A.

^[24] The distance or cost of passing from A to B is not equal to the distance or cost of passing from B to A.

^[25] cf. Lenstra, J.K., 1977: Sequencing by Enumerative Methods

^[26] “The Euclidean distance for two points x = (x1,...,xn) and y = (y1,...,yn) in Euclidean n-space is defined as ”, cf. Wikipedia, the free encyclopedia, 2005: Euclidean distance

^[27] cf. Papadimitriou, C.H., 1977: Euclidean TSP is NP-complete

^[28] cf. Beutel, P., 1981: Das asymmetrische traveling salesman problem, p. 2

^[29] cf. Rardin, R., 1998: Optimization in Operations Research, pp. 586-594

^[30] cf. chapter 2.1.1 The basic developments of the Vehicle Routing Problem

^[31] cf. Dantzig, G.B. and Ramser, J.H., 1959: The Truck Dispatching Problem

^[32] Domschke describes a routing problem example for a furniture store which wants to serve its customers on a special day and associates this problem “…with the complete undirected graph with nodes N {0}, edges E, and edge-traversal costs cij, {i.j} ∈ E.” [cf. Ralphs, T.K. et. al., 2003: On the Capacitated Vehicle Routing, p. 344], cf. Domschke, W., 1997: Logistik: Rundreisen und Touren, pp. 204 - 205

^[33] cf. Figure 2-2 TSP

^[34] cf. Laporte, Y. N. and Desrochers, M., 1985: Optimal Routing with Capacity and Distance Restrictions, p. 1050

^[35] cf. Ralphs, T.K., Pulleyblank, W.R., and Trotter, L.E. Jr., 2003: On the Capacitated Vehicle Routing, p. 344

^[36] cf. Ralphs, T.K., Pulleyblank, W.R., and Trotter, L.E. Jr., 2003: On the Capacitated Vehicle Routing, p. 344

^[37] The two subchapters above describe the BPP and the TSP.

^[38] cf. Garey, M.R. and Johnson, D.S., 1979: Computers and Intractability: A Guide to the Theory of NP Completeness

^[39] cf. Lenstra, J.K. and Rinnooy Kan, A.H.G., 1981: Complexity of vehicle routing and scheduling problems

^[40] cf. Dror, M. and Trudeau, P., 1990: Split delivery routing

^[41] cf. Ralphs, T.K., Pulleyblank, W.R., and Trotter, L.E. Jr., 2003: On the Capacitated Vehicle Routing, p. 344

^[42] “Operations Research (OR) is the study of how to form mathematical models of complex engineering and management problems and how to analyze them to gain insight about possible solutions.”, cf. Rardin, R., 1998: Optimization in Operations Research, p. 1

^[43] cf.Christofides, N. and Eilon, S., 1969: An algorithm for the vehicle dispatching problem

^[44] cf. Yellow, P., 1970: A computational modification to the savings method of vehicle scheduling

^[45] cf. Wren, A. and Holliday, A., 1972: Computer scheduling of vehicles from one or more depots to a number of delivery points

^[46] cf. Gillett, B.E. and Miller, L.R., 1974: A heuristic for the vehicle-dispatch problem

^[47] cf. Christofides, N., Mingozzi, A. and Toth, P., 1979: Combinatorial Optimization, chapter The Vehicle Routing Problem

^[48] cf. Ho, S.C. and Haugland, D., 2004: A tabu search heuristic for the vehicle routing problem with time windows and split deliveries

^[49] cf. Reimann, M., Doerner, K. and Hartl, R.F., 2003: D-ants: savings based ants divide and conquer the vehicle routing problem

^[50] cf. Toth, P. and Vigo, D., eds., 2002: The Vehicle Routing Problem

^[51] cf. Cordeau, J.-F. et al., 2002 : VRP with Time Windows, p. 157

^[52] cf. Toth, P. and Vigo, D., eds., 2002: The Vehicle Routing Problem, pp. 195-224

^[53] cf. Desaulniers, G. et al., 2002: VRP with Pick and Delivery, pp. 225-242

^[54] cf. Vianna, D.S., Ochi, L.S. and Drummond, L.M.A., 1999: A Parallel Hybrid Evolutionary Metaheuristic for the Period Vehicle Routing Problem

^[55] cf. Beltrami, E. and Bodin, L., 1974: Networks and vehicle routing for municipal waste collection

^[56] cf. Russell, R.A. and Igo, W., 1979: An assignment routing problem

^[57] cf. Christofides, N. and Beasley, J.E., 1984: The Period Routing Problem

^[58] cf. Tan, C.C.R. and Beasley, J.E., 1984: A heuristic algorithm for the period vehicle routing problem

^[59] cf. Fisher, M.L. and Jaikumar, R., 1981: A generalized assignment heuristic for vehicle routing

^[60] cf. Russell, R.A. and Gribbin, D., 1991: A multiphase approach to the period routing problem

^[61] The record-to-record travel (RRT) is a simple stochastic local optimization algorithm.

^[62] cf. Dueck, G., 1990: New optimization heuristics, the great deluge algorithm and the record-record travel

^[63] cf. Chao, I.-M., Golden, B.L., and Wasil, E.,1995: An improved heuristics for the period vehicle routing problem

^[64] cf. Cordeau, J.-F., Gendreau, M., and Laporte, G., 1995: A tabu search heuristic for periodic and multi-depot vehicle routing problems

^[65] cf. Hadjiconstantinou, E. and Baldacci, R., 1998: A multi-depot period vehicle routing problem arising in the utilities sector

^[66] cf. Drummond, L., Ochi, L.S., and Vianna, D.S., 2001: An asynchronous metaheuristic for the period vehicle routing problem

^[67] cf. Shih, L.-H. and Chang, H-C., 2001: A routing scheduling system for infectious waste collection

^[68] cf. Angelelli, E. and Speranza, M.G., 2002: The period vehicle routing problem with intermediate facilities

^[69] cf. Blakeley, F. and Knolmajer, J., 2003: Optimizing the periodic maintenance operations for Schindler Elevator Corporation

^[70] Alegre Martínez, J.F. et al., 2002: Uso de Ejection Chains para el diseño de calendarios de transporte de componentes de automóviles

^[71] “FortMP is a Mathematical Programming system designed to solve large scale Linear Programming (LP), Quadratic Programming (QP), Integer Programming (IP) and variable separable programming including special ordered sets of Type 1 and Type 2 (SOS1 and SOS2) problems. … FortMP is used in Management Science or Operations Research and covers applications such as transportation, chemical engineering, product blending, economic modelling, energy systems, and networks. In short, most industrial applications or research problems involving linear or discrete optimisation are handled by this system.”, OptiRisk Systems, 2004: Introduction

^[72] cf. Baptista, S., Oliveira, R.C., and Zúquete, E., 2002: A period vehicle routing case study, p. 220

^[73] cf. Vianna, D.S., Ochi, L.S. and Drummond, L.M.A., 1999: A Parallel Hybrid Evolutionary Metaheuristic for the Period Vehicle Routing Problem, p. 2

^[74] cf. Mingozzi, A. and Valletta, A., 2003: An exact algorithm for period and multi-depot vehicle routing problems

^[75] Odysseus 2003 was the second international workshop on freight transportation and logistics in Mondello (Palermo), Sicily, Italy.

^[76] cf. Beltrami, E. and Bodin, L., 1974: Networks and vehicle routing for municipal waste collection

^[77] cf. Russell, R.A. and Igo, W., 1979: An assignment routing problem

^[78] The Chinese Postman Problem is a node-based routing problem for just one vehicle, cf. Kwan, M.-K., 1962: Graphic Programming Using Odd or Even Points

^[79] cf. Beltrami, E. and Bodin, L., 1974: Networks and vehicle routing for municipal waste collection, p. 70

^[80] cf. Clarke, G. and Wright, J., 1964: Scheduling of Vehicles from a Central Depot to a Number of Delivery Points

^[81] cf. the beginning of this chapter

^[82] cf. Beltrami, E. and Bodin, L., 1974: Networks and vehicle routing for municipal waste collection, p. 83

^[83] An Euler tour is a graph-based route where each node and each graph is contained once., cf. Larson, R.C. and Odoni, A.R., 1981: Chapter 6: Applications of Network Models in Urban Operations Research, pp. 359-379

^[84] cf. Russell, R.A. and Igo, W., 1979: An assignment routing problem, p. 2

^[85] cf. Figure 2-2 TSP

^[86] “MTOUR is a generalization of the highly successful traveling salesman problem heuristic of Lin and Kernighan…”, cf. Russell, R.A. and Igo, W., 1979: An assignment routing problem, p. 7

^[87] cf. Christofides N. and Beasley, J.E., 1984: The Period Routing Problem

^[88] cf. Russell, R.A. and Gribbin, D., 1991: A multiphase approach to the period routing problem

^[89] cf. Chao, I.-M., Golden, B.L., and Wasil, E.,1995: An improved heuristics for the period vehicle routing problem

^[90] cf. Cordeau, J.-F., Gendreau, M., and Laporte, G., 1995: A tabu search heuristic for periodic and multi-depot vehicle routing problems

^[91] cf. Christofides N. and Beasley, J.E., 1984: The Period Routing Problem, p. 237

^[92] cf. Christofides N. and Beasley, J.E., 1984: The Period Routing Problem, p. 239

^[93] cf. Golden, B.L., Magnanti, T.L., and Nguyen H.Q., 1977: Implementing vehicle routing algorithms, pp. 117-118

^[94] cf. Russell, R.A. and Gribbin, D., 1991: A multiphase approach to the period routing problem

^[95] cf. Russell, R.A. and Gribbin, D., 1991: A multiphase approach to the period routing problem , p. 750

^[96] cf. Fisher, M.L. and Jaikumar, R., 1981: A generalized assignment heuristic for vehicle routing

^[97] cf. Tan, C.C.R. and Beasley, J.E., 1984: A heuristic algorithm for the period vehicle routing problem, pp. 498-499

^[98] Eight test problems are taken from Christofides and Beasley, the other two ones are new problems., cf. Russell, R.A. and Gribbin, D., 1991: A multiphase approach to the period routing problem , p. 751