Solving Min-Max Capacitated Vehicle Routing Problem by Local Search

Son Van Nguyen; Dung Quang Pham; Trung Quoc Bui; Hoang Thanh Nguyen

doi:10.15625/1813-9663/33/1/8846

Author affiliations

Authors

Son Van Nguyen Hanoi University of Science and Technology
Dung Quang Pham Hanoi University of Science and Technology
Trung Quoc Bui Viettel Research and Development Institute
Hoang Thanh Nguyen

DOI:

https://doi.org/10.15625/1813-9663/33/1/8846

Keywords:

vehicle routing, local search, min-max vehicle routing, combinatorial optimization

Abstract

Vehicle routing is a class of combinatorial optimization problems in transportation and logistics. Min-max capacitated vehicle routing is a problem of this class in which the length of the longest route must be minimized. This paper investigates local search approach for solving the min-max capacitated vehicle routing problem with different neighborhood structures. We also propose a combined function instead of the objective function itself for controlling the local search. Experimental results on different datasets show the efficiency of our proposed algorithms compared to previous techniques.

Metrics

Metrics Loading ...

References

@article{pham2016,

title = "A Constraint-Based Local Search for offline and online general vehicle routing",

journal = "International Journal on Artificial Intelligence Tools. To appear",

volume = "",

number = "",

pages = "",

year = "2016",

note = "",

issn = "",

doi = "",

url = "",

author = "Pham Quang Dung and Le Kim Thu and Nguyen Thanh Hoang and Pham Van Dinh and Bui Quoc Trung",

keywords = "",

abstract = ""

}

@article{LAPORTE1992345,

title = "The vehicle routing problem: An overview of exact and approximate algorithms",

journal = "European Journal of Operational Research",

volume = "59",

number = "3",

pages = "345 - 358",

year = "1992",

note = "",

issn = "0377-2217",

doi = "http://dx.doi.org/10.1016/0377-2217(92)90192-C",

url = "http://www.sciencedirect.com/science/article/pii/037722179290192C",

author = "Gilbert Laporte",

keywords = "Vehicle Routing Problem",

keywords = "survey",

abstract = "In this paper, some of the main known results relative to the Vehicle Routing Problem are surveyed. The paper is organized as follows: (1) definition; (2) exact algorithms; (3) heuristic algorithms; (4) conclusion."

}

@book{bookvrp,

author = {Golden, Bruce L., Raghavan, S., Wasil, Edward A.},

title = {The Vehicle Routing Problem: Latest Advances and New Challenges},

publisher = {Springer},

year = 2008,

series = 43,

address = {The address},

isbn = {978-0-387-77778-8}

}

@Article{Ralphs2003,

author="Ralphs, T.K.

and Kopman, L.

and Pulleyblank, W.R.

and Trotter, L.E.",

title="On the capacitated vehicle routing problem",

journal="Mathematical Programming",

year="2003",

volume="94",

number="2",

pages="343--359",

issn="1436-4646",

doi="10.1007/s10107-002-0323-0",

url="http://dx.doi.org/10.1007/s10107-002-0323-0"

}

@article{doi:10.1287/opre.40.2.342,

author = {Martin Desrochers and Jacques Desrosiers and Marius Solomon},

title = {A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows},

journal = {Operations Research},

volume = {40},

number = {2},

pages = {342-354},

year = {1992},

doi = {10.1287/opre.40.2.342},

URL = {

http://dx.doi.org/10.1287/opre.40.2.342

},

eprint = {

http://dx.doi.org/10.1287/opre.40.2.342

}

@article{Golden:1997:AMH:250083.250089,

author = {Golden, Bruce L. and Laporte, Gilbert and Taillard, '{E}ric D.},

title = {An Adaptive Memory Heuristic for a Class of Vehicle Routing Problems with Minmax Objective},

journal = {Comput. Oper. Res.},

issue_date = {May 1997},

volume = {24},

number = {5},

month = may,

year = {1997},

issn = {0305-0548},

pages = {445--452},

numpages = {8},

url = {http://dx.doi.org/10.1016/S0305-0548(96)00065-2},

doi = {10.1016/S0305-0548(96)00065-2},

acmid = {250089},

publisher = {Elsevier Science Ltd.},

address = {Oxford, UK, UK},

}

@article{Applegate:2002,

author = {Applegate, David and Cook, William and Dash, Sanjeeb and Rohe, Andr{'e}},

title = {Solution of a Min-Max Vehicle Routing Problem},

journal = {INFORMS J. on Computing},

issue_date = {April 2002},

volume = {14},

number = {2},

month = apr,

year = {2002},

issn = {1526-5528},

pages = {132--143},

numpages = {12},

url = {http://dx.doi.org/10.1287/ijoc.14.2.132.118},

doi = {10.1287/ijoc.14.2.132.118},

acmid = {769683},

publisher = {INFORMS},

address = {Institute for Operations Research and the Management Sciences (INFORMS), Linthicum, Maryland, USA},

keywords = {Combinatorial Optimization, distributed Computing, integer Programming, vehicle Routing},

}

@article{ARKIN20061,

title = "Approximations for minimum and min-max vehicle routing problems",

journal = "Journal of Algorithms",

volume = "59",

number = "1",

pages = "1 - 18",

year = "2006",

note = "",

issn = "0196-6774",

doi = "http://dx.doi.org/10.1016/j.jalgor.2005.01.007",

url = "http://www.sciencedirect.com/science/article/pii/S0196677405000258",

author = "Esther M. Arkin and Refael Hassin and Asaf Levin",

keywords = "Approximation algorithms",

keywords = "Edge-routing",

keywords = "Vehicle routing problem",

keywords = "Min-max problems",

abstract = "We consider a variety of vehicle routing problems. The input to a problem consists of a graph G=(N,E) and edge lengths l(e), e∈E. Customers located at the vertices have to be visited by a set of vehicles. Two important parameters are k the number of vehicles, and λ the longest distance traveled by a vehicle. We consider two types of problems. (1) Given a bound λ on the length of each path, find a minimum sized collection of paths that cover all the vertices of the graph, or all the edges from a given subset of edges of the input graph. We also consider a variation where it is desired to cover N by a minimum number of stars of length bounded by λ. (2) Given a number k find a collection of k paths that cover either the vertex set of the graph or a given subset of edges. The goal here is to minimize λ, the maximum travel distance. For all these problems we provide constant ratio approximation algorithms and prove their NP-hardness."

}

@electronic{abc,

author = "Hemel, T., S. van Erk, P. Jenniskens",

title = "The Manhattan Project",

url = "http://www.win.tue.nl/whizzkids/1996/tsp.html"

}

@electronic{xyz,

author = "Hall, R. W.",

title = "Vehicle Routing Software Survey",

url = "Retrieved August 16, 2013, from http://www.orms-today.org/surveys/Vehicle_Routing/vrss.html "

}

@article{doi:10.1287/trsc.29.3.267,

author = {Paulo M. França and Michel Gendreau and Gilbert Laporte and Felipe M. Müller},

title = {The m-Traveling Salesman Problem with Minmax Objective},

journal = {Transportation Science},

volume = {29},

number = {3},

pages = {267-275},

year = {1995},

doi = {10.1287/trsc.29.3.267},

URL = {

http://dx.doi.org/10.1287/trsc.29.3.267

},

eprint = {

http://dx.doi.org/10.1287/trsc.29.3.267

}

,

abstract = { This article proposes algorithms for the Minmax version of the m-Traveling Salesman Problem in which the objective is to minimize the length of the longest route. A tabu search heuristic and two exact search schemes are developed. Problems involving up to 50 vertices are solved to optimality. }

}

@article{Ren2011,

author = {Chunyu Ren},

title = {Solving Min-Max Vehicle Routing Problem},

journal = {JOURNAL OF SOFTWARE},

volume = {6},

number = {9},

year = {2011}

}

@Inbook{DelgadoSerna2001,

author="Delgado Serna, Cristina R.

and Pacheco Bonrostro, Joaqu{'i}n",

editor="Vo{ss}, Stefan

and Daduna, Joachim R.",

title="Minmax Vehicle Routing Problems: Application to School Transport in the Province of Burgos",

bookTitle="Computer-Aided Scheduling of Public Transport",

year="2001",

publisher="Springer Berlin Heidelberg",

address="Berlin, Heidelberg",

pages="297--317",

isbn="978-3-642-56423-9",

doi="10.1007/978-3-642-56423-9_17",

url="http://dx.doi.org/10.1007/978-3-642-56423-9_17"

}

@article{doi:10.1287/opre.1040.0111,

author = {R. Baldacci and E. Hadjiconstantinou and A. Mingozzi},

title = {An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation},

journal = {Operations Research},

volume = {52},

number = {5},

pages = {723-738},

year = {2004},

doi = {10.1287/opre.1040.0111},

URL = {

http://dx.doi.org/10.1287/opre.1040.0111

},

eprint = {

http://dx.doi.org/10.1287/opre.1040.0111

}

,

abstract = { The capacitated vehicle routing problem (CVRP) is the problem in which a set of identical vehicles located at a central depot is to be optimally routed to supply customers with known demands subject to vehicle capacity constraints. In this paper, we describe a new integer programming formulation for the CVRP based on a two-commodity network flow approach. We present a lower bound derived from the linear programming (LP) relaxation of the new formulation which is improved by adding valid inequalities in a cutting-plane fashion. Moreover, we present a comparison between the new lower bound and lower bounds derived from the LP relaxations of different CVRP formulations proposed in the literature. A new branch-and-cut algorithm for the optimal solution of the CVRP is described. Computational results are reported for a set of test problems derived from the literature and for new randomly generated problems. }

}

@Article{Fukasawa2006,

author="Fukasawa, Ricardo

and Longo, Humberto

and Lysgaard, Jens

and Arag{~a}o, Marcus Poggi de

and Reis, Marcelo

and Uchoa, Eduardo

and Werneck, Renato F.",

title="Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem",

journal="Mathematical Programming",

year="2006",

volume="106",

number="3",

pages="491--511",

abstract="The best exact algorithms for the Capacitated Vehicle Routing Problem (CVRP) have been based on either branch-and-cut or Lagrangean relaxation/column generation. This paper presents an algorithm that combines both approaches: it works over the intersection of two polytopes, one associated with a traditional Lagrangean relaxation over q-routes, the other defined by bound, degree and capacity constraints. This is equivalent to a linear program with exponentially many variables and constraints that can lead to lower bounds that are superior to those given by previous methods. The resulting branch-and-cut-and-price algorithm can solve to optimality all instances from the literature with up to 135 vertices. This more than doubles the size of the instances that can be consistently solved.",

issn="1436-4646",

doi="10.1007/s10107-005-0644-x",

url="http://dx.doi.org/10.1007/s10107-005-0644-x"

}

@article{Marinakis20126807,

title = "Multiple Phase Neighborhood Search-GRASP for the Capacitated Vehicle Routing Problem ",

journal = "Expert Systems with Applications ",

volume = "39",

number = "8",

pages = "6807 - 6815",

year = "2012",

note = "",

issn = "0957-4174",

doi = "http://dx.doi.org/10.1016/j.eswa.2012.01.015",

url = "http://www.sciencedirect.com/science/article/pii/S0957417412000176",

author = "Yannis Marinakis",

keywords = "Vehicle Routing Problem",

keywords = "Greedy Randomized Adaptive Search Procedure",

keywords = "Expanding Neighborhood Search",

keywords = "Langrangean Relaxation ",

abstract = "Greedy Randomized Adaptive Search Procedure (GRASP) has been proved to be a very efficient algorithm for the solution of the Traveling Salesman Problem. Also, it has been proved that expanding the local search with the use of two or more different local search strategies helps the algorithm to avoid trapping in a local optimum. In this paper, a new modified version of GRASP, called Multiple Phase Neighborhood Search-GRASP (MPNS-GRASP), for the solution of the Vehicle Routing Problem is proposed. In this method, a stopping criterion based on Lagrangean Relaxation and Subgradient Optimization is utilized. In addition, a different way for expanding the neighborhood search is used based on a new strategy, the Circle Restricted Local Search Moves strategy. The algorithm was tested on two sets of benchmark instances and gave very satisfactory results. In both sets of instances the results have solution qualities with average values near to the optimum values and in a number of them the algorithm finds the optimum. The computational time of the algorithm is decreased significantly compared to other heuristic and metaheuristic algorithms due to the fact that the new strategy, the Expanding Neighborhood Search Strategy, is used. "

}

@article{Baldacci20121,

title = "Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints ",

journal = "European Journal of Operational Research ",

volume = "218",

number = "1",

pages = "1 - 6",

year = "2012",

note = "",

issn = "0377-2217",

doi = "http://dx.doi.org/10.1016/j.ejor.2011.07.037",

url = "http://www.sciencedirect.com/science/article/pii/S0377221711006692",

author = "Roberto Baldacci and Aristide Mingozzi and Roberto Roberti",

keywords = "Vehicle routing",

keywords = "Exact algorithms",

keywords = "Survey ",

abstract = "This paper provides a review of the recent developments that had a major impact on the current state-of-the-art exact algorithms for the vehicle routing problem (VRP). The paper reviews mathematical formulations, relaxations and recent exact methods for two of the most important variants of the VRP: the capacitated {VRP} (CVRP) and the {VRP} with time windows (VRPTW). The paper also reports a comparison of the computational performances of the different exact algorithms for the {CVRP} and VRPTW. "

}

@article{Jin2012441,

title = "A parallel multi-neighborhood cooperative tabu search for capacitated vehicle routing problems ",

journal = "European Journal of Operational Research ",

volume = "222",

number = "3",

pages = "441 - 451",

year = "2012",

note = "",

issn = "0377-2217",

doi = "http://dx.doi.org/10.1016/j.ejor.2012.05.025",

url = "http://www.sciencedirect.com/science/article/pii/S037722171200375X",

author = "Jianyong Jin and Teodor Gabriel Crainic and Arne Løkketangen",

keywords = "Routing",

keywords = "Parallel metaheuristics",

keywords = "Multi-neighborhood",

keywords = "Cooperative search",

keywords = "Solution pool ",

abstract = "This paper presents a parallel tabu search algorithm that utilizes several different neighborhood structures for solving the capacitated vehicle routing problem. Single neighborhood or neighborhood combinations are encapsulated in tabu search threads and they cooperate through a solution pool for the purpose of exploiting their joint power. The computational experiments on 32 large scale benchmark instances show that the proposed method is highly effective and competitive, providing new best solutions to four instances while the average deviation of all best solutions found from the collective best results reported in the literature is about 0.22%. We are also able to associate the beneficial use of special neighborhoods with some test instance characteristics and uncover some sources of the collective power of multi-neighborhood cooperation. "

}

@article{Szeto2011126,

title = "An artificial bee colony algorithm for the capacitated vehicle routing problem ",

journal = "European Journal of Operational Research ",

volume = "215",

number = "1",

pages = "126 - 135",

year = "2011",

note = "",

issn = "0377-2217",

doi = "http://dx.doi.org/10.1016/j.ejor.2011.06.006",

url = "http://www.sciencedirect.com/science/article/pii/S0377221711005121",

author = "W.Y. Szeto and Yongzhong Wu and Sin C. Ho",

keywords = "Routing",

keywords = "Artificial bee colony",

keywords = "Metaheuristic ",

abstract = "This paper introduces an artificial bee colony heuristic for solving the capacitated vehicle routing problem. The artificial bee colony heuristic is a swarm-based heuristic, which mimics the foraging behavior of a honey bee swarm. An enhanced version of the artificial bee colony heuristic is also proposed to improve the solution quality of the original version. The performance of the enhanced heuristic is evaluated on two sets of standard benchmark instances, and compared with the original artificial bee colony heuristic. The computational results show that the enhanced heuristic outperforms the original one, and can produce good solutions when compared with the existing heuristics. These results seem to indicate that the enhanced heuristic is an alternative to solve the capacitated vehicle routing problem. "

}

@article{Liu2010950,

title = "Two-phase heuristic algorithms for full truckloads multi-depot capacitated vehicle routing problem in carrier collaboration ",

journal = "Computers & Operations Research ",

volume = "37",

number = "5",

pages = "950 - 959",

year = "2010",

note = "Disruption Management ",

issn = "0305-0548",

doi = "http://dx.doi.org/10.1016/j.cor.2009.08.002",

url = "http://www.sciencedirect.com/science/article/pii/S0305054809001968",

author = "Ran Liu and Zhibin Jiang and Richard Y.K. Fung and Feng Chen and Xiao Liu",

keywords = "Collaborative transportation",

keywords = "Multi-depot",

keywords = "Full truckloads",

keywords = "Lower bound",

keywords = "Heuristic ",

abstract = "Collaborative transportation, as an emerging new mode, represents one of the major developing trends of transportation systems. Focusing on the full truckloads multi-depot capacitated vehicle routing problem in carrier collaboration, this paper proposes a mathematical programming model and its corresponding graph theory model, with the objective of minimizing empty vehicle movements. A two-phase greedy algorithm is given to solve practical large-scale problems. In the first phase, a set of directed cycles is created to fulfil the transportation orders. In the second phase, chains that are composed of cycles are generated. Furthermore, a set of local search strategies is put forward to improve the initial results. To evaluate the performance of the proposed algorithms, two lower bounds are developed. Finally, computational experiments on various randomly generated problems are conducted. The results show that the proposed methods are effective and the algorithms can provide reasonable solutions within an acceptable computational time. "

}

@incollection{incollection,

author = {Gendreau, M., Laporte, G., Potvin, J.-Y},

title = {Metaheuristics for the capacitated VRP},

booktitle = {The Vehicle Routing Problem},

publisher = {SIAM Monographs on Discrete Mathematics and Applications},

year = 2002,

editor = {Toth, P., Vigo D},

volume = 9

}

@article{Suresh2012,

title = "A Survey on the Vehicle Routing Problem and Its Variants",

journal = "Intelligent Information Management",

volume = "4",

number = "3",

pages = "66-74",

year = "2012",

author = "S. Kumar and R. Panneerselvam",

}

@article{ref12,

author = {Br"{a}ysy, Olli and Gendreau, Michel},

title = {Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms},

journal = {Transportation Science},

issue_date = {February 2005},

volume = {39},

number = {1},

month = feb,

year = {2005},

issn = {1526-5447},

pages = {104--118},

numpages = {15},

url = {http://dx.doi.org/10.1287/trsc.1030.0056},

doi = {10.1287/trsc.1030.0056},

acmid = {1247233},

publisher = {INFORMS},

address = {Institute for Operations Research and the Management Sciences (INFORMS), Linthicum, Maryland, USA},

keywords = {genetic algorithms, heuristics, local search metaheuristics, tabu search, time windows, vehicle routing},

}

@article{ref13,

author = {E. Taillard, P. Badeau, M. Gendreau, F. Guertin and J.-Y. Potvin},

title = {A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows},

journal = {Transportation Science},

volume = {31},

number = {2},

month = feb,

year = {1997},

issn = {1526-5447},

pages = {170--186}

}

@Article{ref14,

author="Chiang, Wen-Chyuan

and Russell, Robert A.",

title="Simulated annealing metaheuristics for the vehicle routing problem with time windows",

journal="Annals of Operations Research",

year="1996",

volume="63",

number="1",

pages="3--27",

abstract="This paper develops simulated annealing metaheuristics for the vehicle routing and scheduling problem with time window constraints. Two different neighborhood structures, the $lambda$-interchange mechanism of Osman and thek-node interchange process of Christofides and Beasley, are implemented. The enhancement of the annealing process with a short-term memory function via a tabu list is examined as a basis for improving the metaheuristic approach. Computational results on test problems from the literature as well as large-scale real-world problem are reported. The metaheuristics achieve solutions that compare favorably with previously reported results.",

issn="1572-9338",

doi="10.1007/BF02601637",

url="http://dx.doi.org/10.1007/BF02601637"

}

@article{ref16,

author = {Jean-Yves Potvin and Samy Bengio},

title = {The Vehicle Routing Problem with Time Windows Part II: Genetic Search},

journal = {INFORMS Journal on Computing},

volume = {8},

number = {2},

pages = {165-172},

year = {1996},

doi = {10.1287/ijoc.8.2.165},

URL = {

http://dx.doi.org/10.1287/ijoc.8.2.165

},

eprint = {

http://dx.doi.org/10.1287/ijoc.8.2.165

}

,

abstract = { This paper is the second part of a work on the application of new search techniques for the vehicle routing problem with time windows. It describes GENEROUS, the GENEtic ROUting System, which is based on the natural evolution paradigm. Under this paradigm, a population of solutions evolves from one generation to the next by “mating” parent solutions to form new offspring solutions that exhibit characteristics inherited from their parents. For this vehicle routing application, a specialized methodology is devised for merging two vehicle routing solutions into a single solution that is likely to be feasible with respect to the time window constraints. Computational results on a standard set of test problems are reported, and comparisons are provided with other heuristics. }

}

@article{ref21,

author = {George Kontoravdis and Jonathan F. Bard},

title = {A GRASP for the Vehicle Routing Problem with Time Windows},

journal = {ORSA Journal on Computing},

volume = {7},

number = {1},

pages = {10-23},

year = {1995},

doi = {10.1287/ijoc.7.1.10},

URL = {

http://dx.doi.org/10.1287/ijoc.7.1.10

},

eprint = {

http://dx.doi.org/10.1287/ijoc.7.1.10

}

,

abstract = { This paper addresses the problem of finding the minimum number of vehicles required to visit a set of nodes subject to time window constraints. A secondary objective is to minimize the total distance traveled. Each node requires a predetermined amount of service in the form of pickups and deliveries. The fleet is homogeneous and is located at a common depot. Vehicle capacity is finite and split service is not permitted. A greedy randomized adaptive search procedure (GRASP) is used to obtain feasible solutions. Results are reported for standard 100 node data sets as well as for a number of real-world problems with up to 417 customers. The findings indicate that, in general, the proposed procedure outperforms current techniques and requires only a small fraction of the time taken by exact methods. To gauge the quality of the solutions, three different lower bounding heuristics were developed. The first considers the “bin packing” aspect of the problem with regard to vehicle capacity; the second is based on the maximum clique associated with the customers' incompatibility graph; the third independently exploits the time window constraints. Using these heuristics, it is empirically demonstrated that the optimum is found in almost all cases involving balanced service and tight capacity constraints and a significant proportion of the remainder. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499. }

}

@article{ref22,

author = {F.-H. Liu and S.-Y. Shen},

title = {The Fleet Size and Mix Vehicle Routing Problem with Time Windows},

journal = { Journal of the Operational Research Society},

volume = {50},

year = {1999},

pages = {721--732}

}

@INPROCEEDINGS{ref23,

author = {Luca Maria Gambardella and Éric Taillard and Giovanni Agazzi},

title = {MACS-VRPTW: A Multiple Colony System For Vehicle Routing Problems With Time Windows},

booktitle = {New Ideas in Optimization},

year = {1999},

pages = {63--76},

publisher = {McGraw-Hill}

}

@article{ref25,

title = "A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows ",

journal = "European Journal of Operational Research ",

volume = "206",

number = "2",

pages = "341 - 349",

year = "2010",

note = "",

issn = "0377-2217",

doi = "http://dx.doi.org/10.1016/j.ejor.2010.02.037",

url = "http://www.sciencedirect.com/science/article/pii/S0377221710001700",

author = "Gabriel Gutiérrez-Jarpa and Guy Desaulniers and Gilbert Laporte and Vladimir Marianov",

keywords = "Transportation",

keywords = "Vehicle routing",

keywords = "Deliveries and selective pickups",

keywords = "Time windows",

keywords = "Branch-and-price",

keywords = "Shortest paths with resources ",

abstract = "In the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows, the set of customers is the union of delivery customers and pickup customers. A fleet of identical capacitated vehicles based at the depot must perform all deliveries and profitable pickups while respecting time windows. The objective is to minimize routing costs, minus the revenue associated with the pickups. Five variants of the problem are considered according to the order imposed on deliveries and pickups. An exact branch-and-price algorithm is developed for the problem. Computational results are reported for instances containing up to 100 customers. "

}

@article{Gendreau2006157,

title = "Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries ",

journal = "Transportation Research Part C: Emerging Technologies ",

volume = "14",

number = "3",

pages = "157 - 174",

year = "2006",

note = "",

issn = "0968-090X",

doi = "http://dx.doi.org/10.1016/j.trc.2006.03.002",

url = "http://www.sciencedirect.com/science/article/pii/S0968090X06000349",

author = "Michel Gendreau and François Guertin and Jean-Yves Potvin and René Séguin",

keywords = "Vehicle dispatching",

keywords = "Real-time",

keywords = "Tabu search",

keywords = "Neighborhood",

keywords = "Ejection chains",

keywords = "Parallel computing ",

abstract = "This paper proposes neighborhood search heuristics to optimize the planned routes of vehicles in a context where new requests, with a pick-up and a delivery location, occur in real-time. Within this framework, new solutions are explored through a neighborhood structure based on ejection chains. Numerical results show the benefits of these procedures in a real-time context. The impact of a master–slave parallelization scheme, using an increasing number of processors, is also investigated. "

}

@article{doi:10.1287/mnsc.6.1.80,

author = {G. B. Dantzig and J. H. Ramser},

title = {The Truck Dispatching Problem},

journal = {Management Science},

volume = {6},

number = {1},

pages = {80-91},

year = {1959},

doi = {10.1287/mnsc.6.1.80},

URL = {

http://dx.doi.org/10.1287/mnsc.6.1.80

},

eprint = {

http://dx.doi.org/10.1287/mnsc.6.1.80

}

,

abstract = { The paper is concerned with the optimum routing of a fleet of gasoline delivery trucks between a bulk terminal and a large number of service stations supplied by the terminal. The shortest routes between any two points in the system are given and a demand for one or several products is specified for a number of stations within the distribution system. It is desired to find a way to assign stations to trucks in such a manner that station demands are satisfied and total mileage covered by the fleet is a minimum A procedure based on a linear programming formulation is given for obtaining a near optimal solution. The calculations may be readily performed by hand or by an automatic digital computing machine. No practical applications of the method have been made as yet. A number of trial problems have been calculated, however. }

}

@article{Eksioglu20091472,

title = "The vehicle routing problem: A taxonomic review ",

journal = "Computers & Industrial Engineering ",

volume = "57",

number = "4",

pages = "1472 - 1483",

year = "2009",

note = "",

issn = "0360-8352",

doi = "http://dx.doi.org/10.1016/j.cie.2009.05.009",

url = "http://www.sciencedirect.com/science/article/pii/S0360835209001405",

author = "Burak Eksioglu and Arif Volkan Vural and Arnold Reisman",

keywords = "Routing",

keywords = "Vehicle routing",

keywords = "VRP",

keywords = "Taxonomy",

keywords = "Classification ",

abstract = "This paper presents a methodology for classifying the literature of the Vehicle Routing Problem (VRP). {VRP} as a field of study and practice is defined quite broadly. It is considered to encompass all of the managerial, physical, geographical, and informational considerations as well as the theoretic disciplines impacting this ever emerging-field. Over its lifespan the {VRP} literature has become quite disjointed and disparate. Keeping track of its development has become difficult because its subject matter transcends several academic disciplines and professions that range from algorithm design to traffic management. Consequently, this paper defines VRP’s domain in its entirety, accomplishes an all-encompassing taxonomy for the {VRP} literature, and delineates all of VRP’s facets in a parsimonious and discriminating manner. Sample articles chosen for their disparity are classified to illustrate the descriptive power and parsimony of the taxonomy. Moreover, all previously published {VRP} taxonomies are shown to be relatively myopic; that is, they are subsumed by what is herein presented. Because the {VRP} literature encompasses esoteric and highly theoretical articles at one extremum and descriptions of actual applications at the other, the article sampling includes the entire range of the {VRP} literature. "

}

@article{groer2010,

title = "A library of local search heuristics for the vehicle

routing problem",

journal = "Math. Prog. Comp.",

volume = "",

number = "2",

pages = "79 - 101",

year = "2010",

note = "",

issn = "",

doi = "",