An Extension of the Lin-Kernighan-Helsgaun TSP Solver for
Constrained Traveling Salesman and
Vehicle Routing Problems
Keld Helsgaun
E-mail: keld@ruc.dk
Department of Computer Science
Roskilde University
DK-4000 Roskilde, Denmark
December 2017
Abstract
This report describes the implementation of an extension of the Lin-Kernighan-Helsgaun TSP
solver for solving constrained traveling salesman and vehicle routing problems. The extension,
which is called LKH-3, is able to solve a variety of well-known problems, including thesequential ordering problem (SOP), the traveling repairman problem (TRP), variants of themultiple travel-ing salesman problem (mTSP), as well as vehicle routing problems (VRPs) withcapacity, time windows, pickup-and-delivery and distance constraints. The implementation of
LKH-3 builds on the idea of transforming the problems into standard symmetric travelingfromthe literaturethat constraints
LKH-3 is effective.
known solutions
often obtained,
salesmanproblemshas
andshownhandlingby meansBestof penalty
functions.areExtensive
testingandin some cases,
new best solutions are found. The program is free of charge for academic andon benchmark
instancesnon-commercial use and can be downloaded in source code. A comprehensive library of benchmark instances and the best obtained results for these instances can also be downloaded.

1. Introduction
The Lin-Kernighan-Helsgaun TSP solver, LKH [1, 2], is a state-of-the-art heuristic solver for thetraveling salesman problem. LKH implements a powerful local search heuristic for the TSP based on
the variable depth local search of Lin and Kernighan [3]. LKH has produced optimal solutions for all
solved problems we have been able to obtain; including an 85,900-city instance (at the time of writing, the largest nontrivial instance solved to optimality). Furthermore, the algorithm has improved
the best known solutions for a series of large-scale instances with unknown optima, among these a
1,904,711-city instance (World TSP).
However, in many practical situations, the TSP has additional constraints such as limited resources,
time windows and precedence constraints. Since the current version of LKH, LKH-2, is highly
customized for the standard TSP and cannot accommodate constraints, its usage is extremely limitedin these situations. Furthermore, solving problems that involve multiple traveling salesmen is notstraightforward.
This is the motivation for extending LKH-2 with facilities handling constraints and multiple travelingsalesmen. The extension, named LKH-3, is currently able to solve the following problem types:

1

ACVRP: Asymmetric capacitated vehicle routing problem
BWTSP: Black and white traveling salesman problem
CCVRP: Cumulative capacitated vehicle routing problem
CVRP: Capacitated vehicle routing problem
CVRPTW: Capacitated vehicle routing problem with time windows
DCVRP: Distance constrained capacitated vehicle routing problem
1-PDTSP: One-commodity pickup-and-delivery traveling salesman problem
m-PDTSP: Multi-commodity pickup-and-delivery traveling salesman problem
m1-PDTSP: Multi-commodity one-to-one pickup-and-delivery traveling salesman problem
MTRP: Multiple traveling repairman problem
MTRPD: Multiple traveling repairman problem with distance constraints
mTSP: Multiple traveling salesmen problem
OVRP: Open vehicle routing problem
PDPTW: Pickup-and-delivery problem with time windows
PDTSP: Pickup-and-delivery traveling salesman problem
PDTSPF: Pickup-and-delivery traveling salesman problem with FIFO loading
PDTSPL: Pickup-and-delivery traveling salesman problem with LIFO loading
RCTVRP: Risk-constrained cash-in-transit vehicle routing problem
RCTVRPTW: Risk-constrained cash-in-transit vehicle routing with time windows
SOP: Sequential ordering problem
TRP: Traveling repairman problem
TSPPD: Traveling salesman problem with pickups and deliveries
TSPTW: Traveling salesman problem with time windows
VRPB: Vehicle routing problem with backhauls
VRPBTW: Vehicle routing problem with backhauls and time windows
VRPMPD: Vehicle routing problem with mixed pickup and delivery
VRPMPDTW: Vehicle routing problem with mixed pickup and delivery and time windows
VRPSPD: Vehicle routing problem with simultaneous pickup and delivery
VRPSPDTW: Vehicle routing problem with simultaneous pickup-delivery and time windows
Extensive testing on benchmark instances from the literature has shown that LKH-3 is effective. Bestknown solutions are often obtained, and in some cases, new best solutions are found.
The next sections describe the implementation of LKH-3.

2

2. Basic ideas
2.1 Transformations
An asymmetric problem with n cities is transformed into a symmetric problem with 2n cities using
the transformation method of Jonker and Volgenant [4]. This transformation method is already implemented in LKH-2 and has been very successful for solving ATSP [5]. Note in this connection thatsome of the problems to be solved by LKH-3 are best conceived as asymmetric problems, even if thecosts are symmetric. This is for example the case for problems with time windows. These problems
are first transformed by LKH-3 to asymmetric problems before they are transformed to symmetricproblems. A positive side effect of this approach is that LKH-3 is able to solve asymmetric versionsof these problem types.
A vehicle routing problem usually involves more than one vehicle and may therefore be conceived
as a multiple traveling salesman problem. Fortunately, a multiple traveling salesman problem with asingle home city (depot) can easily be transformed to a standard traveling salesman problem [6].
A symmetric TSP with m salesmen can be solved using a symmetric TSP augmented with m - 1
copies of the home city, where infinite costs are assigned between home cities [7]. For those symmetric problems that are not transformed to asymmetric problems, LKH-3 uses the improved transformation by Jonker and Volgenant [8].
2.2 Penalty functions
LKH-3 uses penalty functions for handling constraints. A penalty function returns a value that depends on how much the given constraints are violated. In contrast to the traditional usage of penalty
functions, where a penalty value is added to (or multiplied with) the objective value, these two values
are kept separate by LKH-3. Associated with each tour is a pair (P, C), where P is the penalty of thetour, and C is its cost. Let T1 and T2 be two tours with associated pairs (P1, C1) and (P2, C2). Then T1
is better than T2 if (P1 < P2)  (P1 = P2  C1 < C2). In other words: minimizing penalty is the primaryobjective, whereas minimizing cost is the secondary. A penalty function has been implemented foreach problem type.
When a move on a given tour produces a better, the move is said to be improving. To check that amove is improving, the move is made, and the penalty and cost for the resulting tour are computedand compared with the penalty and cost of the original tour. If no improvement is found, the move isretracted.
2.3 Special moves
The data structure used in LKH for tour representation, a two-level tree [9], gives an average timecomplexity of O(√𝑁) for making a move, where N is the number of cities. The average time complexity for move retraction is the same since this is performed by an inverted move.
The most time-consuming part of the move checking procedure is the penalty computation. Its worstcase time complexity is O(N). Speedup may often be achieved by using the fact that the computation
may be terminated as soon as the value becomes greater than the value for the current best tour. Some
speedup might also be achieved by starting the computation in the route that most recently caused
the computation to terminate However, worst-case time complexity is still O(N).

3The time complexity of the penalty computation necessitates that the number of moves to be checkedshould be small. The advanced high-order move types available in LKH can be used, but they willoften be too time consuming. Therefore, a new specially designed 5-opt move generator is provided.
Compared with the 5-opt move generator in LKH-2, the new generator mainly considers moves that
do not reverse a segment on the tour. Furthermore, it adds a restricted exploration of sequential 4and 5-opt moves as well as non-sequential 4- and 6-opt moves. In this way, the number of moves toconsider is reduced considerably. Note that restricting the move search in this way has no consequence for asymmetric problem instances since moves that reverse a segment are forbidden anyway.
3. Input
LKH-3 includes code for reading problem instances and for printing solutions. Input is given in two
separate files:(1) a problem file and(2) a parameter file
3.1 The problem file
The problem file contains a specification of the problem instance to be solved. The file format is anextension of the TSPLIB format [10]. A problem file consists of a specification part and of a data
part. The specification part contains information on the file format and on its contents. The data partcontains explicit data.
3.1.1 The specification partAll entries in this section are of the form <keyword> : <value>, where <keyword> denotes an alphanumerical keyword and <value> denotes alphanumerical or numerical data. Below is given a listof the new keywords in LKH-3:
SALESMEN : <integer>
Specifies the number of salesmen (= vehicles).
VEHICLES : <integer>
Specifies the number of vehicles (= salesmen).
DISTANCE : <real>
The maximum length allowed for each route in a vehicle route problem.
RISK_THRESHOLD : <integer>
The maximum risk allowed for each route in a risk constrained problem.
SCALE : <integer>
A scale factor for Euclidean instances. Distances are multiplied by this factor.
Note that the keyword CAPACITY, which is used for specifying the vehicle capacity, belongs to theoriginal version of the TSPLIB format.

4New distance functions have also been added:
EXACT_2D, EXACT_3D:
Euclidean distance multiplied by 1000 and rounded to nearest integer.
FLOOR_2D, FLOOR_3D:
Euclidean distance rounded down to the last integer.
TOR_2D, TOR_3D:
Toroidal distance.
3.1.2 The data part
Depending on the choice of specifications, some additional data may be required. These data are
given in corresponding data sections following the specification part. Each data section begins withthe corresponding keyword. The length of the section is either implicitly known from the format
specification, or the section is terminated by an appropriate endof-section identifier.
LKH-3 extends the TSPLIB format with the following data sections:
BACKHAUL_SECTION :This section is used for specifying VRPB instances. It contains a list of backhaul nodes. Thissection is terminated by a -1.
PICKUP_AND_DELIVERY_SECTION :This section is used for specifying pickup-and-delivery instances. Each line is of the form
<integer> <integer> <real> <real> <real> <integer> <integer>
The first integer gives the number of the node.
The second integer gives its demand (ignored for PDTSPF, PDTSPL, VRPMPD and
VRPSPD instances).
The third and fourth number give the earliest and latest time for the node.
The fifth number specifies the service time for the node.
The last two integers are used to specify pickup and delivery. For a PDPTW, PDTSP,PDTSPF and PDTSPL instance, the first of these integers gives the index of the pickup sibling, and the second integer gives the index of the delivery sibling. For a VRPMPD and
VRPSPD instance, the two integers simply give the size of the pickup and delivery for thenode.
SERVICE_TIME_SECTION :The service times of all nodes of a CVRP are given in the form (per line)<integer> <real>
The integer specifies a node number, the real its service time. The depot node must also occur
in this section. Its service time is 0.

5

TIME_WINDOW_SECTION :Time windows are given in this section. Each line is of the form
<integer> <real> <real>
The first integer specifies a node number. The two reals specify earliest and latest arrival time
for the node, respectively.
The keyword DEPOT_SECTION, which is used for specifying depots, belongs to the original versionof the TSPLIB format. The section is terminated by a -1. Note, however, that LKH-3 at present only
allows one depot.
3.2 The parameter file
The parameter file contains control parameters for the solution process. The solution process is typically carried out using default values for the parameters. The default values have proven to be adequate in many applications. However, for applications with penalty functions, better performance isachieved by choosing other values. For such applications, experiments have shown that the following
setting works well:
MOVE_TYPE = 5 SPECIAL
GAIN23 = NO
KICKS = 1
KICKTYPE = 4
MAX_SWAPS = 0
POPULATION_SIZE = 10
The specially designed 5-opt move procedure is chosen by setting MOVE_TYPE to 5 SPECIAL.
By setting GAIN23 to NO, the exploration of non-sequential moves at the end of each trial is turned
off. Notice, however, that some non-sequential moves after all are explored by the chosen moveprocedure.
The default perturbation method in LKH is a random walk on the candidate graph. But this method
destroys the tour a lot. Instead, by setting KICKS to 1 and KICK_TYPE to 4, a random doublebridge-kick move is chosen. This move is a non-sequential 4-opt move that replaces only 4 edges on
the tour by 4 non-tour edges.
By setting MAX_SWAPS to 0, no attempts are made to find improving moves of a higher order thanspecified by the basic move type (5 SPECIAL).
The genetic algorithm of LKH with a population size of 10 is used.
The parameter settings above may be chosen by just writing
SPECIALin the beginning of the parameter file.

6

LKH-3 adds the following new or extended parameter settings:
BWTSP = <integer> <integer> [ <integer> ]Specifies the three parameters (B, Q, L) to a BWTSP instance.
B: Number of black nodes.
Q: Maximum number of white nodes on "black-to-black" paths.
L: Maximum length of any "black-to-black" path.
Default: 0 0.
DEPOT = <integer>
Specifies the depot node.
Default: 1.
INITIAL_TOUR_ALGORITHM = { … | CVRP | MTSP | SOP }Specifies the algorithm for obtaining an initial tour.
Default: WALK.
MAKESPAN = { YES | NO }Specifies if makespan optimization is to be used for a TSPTW instance.
Default: NO.
MOVE_TYPE = <integer> [ SPECIAL ]Specifies the move type to be used in local search. An integer value k >= 2 signifies that asequential k-opt move is to be used. The specifier SPECIAL can be given in order to use
specially designed moves. For this type of moves, k must be 3 or 5.
Default: 5.
MTSP_MIN_SIZE = <integer>
Specifies the minimum number of cities each salesman must visit in an mTSP or CVRP instance. If negative, its value is set to
DIMENSION / (ceil(1.0 * DIMENSION / MTSP_MAX_SIZE) + 1)
Default: 1.
MTSP_MAX_SIZE = <integer>
Specifies the maximum number of cities each salesman may visit in an mTSP or CVRP instance.
Default: value of DIMENSION - 1.
MTSP_OBJECTIVE = [ MINMAX | MINMAX_SIZE | MINSUM ]Specifies the objective function type for a multiple traveling salesman problem.
MINMAX- Minimize the length of the longest route.
MINMAX_SIZE - Minimize the size of the largest route.
MINSUM- Minimize the length of the overall tour.
All routes must satisfy the MTSP_MIN_SIZE and MTSP_MAX_SIZE constraints.

7

MTSP_SOLUTION_FILE = <string>Specifies the name of a file where the solution of an mTSP (or VRP) instance is to be written.
SALESMEN = <integer>
Specifies the number of salesmen/vehicles.
Default: 1.
SCALE = <integer>
Scale factor for Euclidean instances.
Default: 1.
SINTEF_SOLUTION_FILE = <string>Specifies the name of a file where the solution of an mTSP or VRP instance is to be written.
The solution is written in SINTEF format.
VEHICLES = <integer>
Specifies the number of vehicles/salesmen.
Default: 1.

8

4. Summary of benchmark tests
LKH-3 has been tested extensively on benchmark instances from the literature. The table below
summarizes the results. The first two columns give the problem type and number of test instances forthis type. The three last columns give the number of times the solution found by LKH-3 was better
than, equal to, or worse than the best known solution (BKS).

Problem type Instances < BKS = BKS > BKS
ACVRP
32
0
32
0
BWTSP
38
0
38
0
CCVRP
164
53
74
37
CVRP
509
44
327
138
CVRPTW
405
2
302
101
DCVRP
22
1
17
4
1-PDTSP
2036
380
1528
78
m-PDTSP
892
118
724
50
m1-PDTSP
1178
21
1157
0
mTSP
127
51
72
4
MTRP
1040
7
1033
0
MTRPD
180
0
180
0
OVRP
111
4
101
6
PDPTW
222
3
180
139
PDTSP
163
5
156
2
PDTSPF
772
47
28
PDTSPL
126
15
97
14
RCTVRP
378
79
283
16
RCTVRPTW
24
0
24
0
SOP
163
9
150
4
TRP
130
21
109
0
TSPPD
600
0
600
0
TSPTW
900
47
853
0
VRPB
149
4
141
4
VRPBTW
15
3
12
0
VRPMPD
70
955
6
VRPMPDTW70953
8VRPSPD
266
20
148
98
VRPSPDTW
68
46
20
2

9

5. Conclusions
LKH-3 is based on the simple idea of transforming the problems to standard traveling salesman problems and handling the involved constraints by means of penalty functions. Despite its simplicity,
extensive testing on benchmark instances from the literature has shown that LKH-3 is effective forsolving a variety of problem types. Best known solutions are often obtained, and in some cases, newbest solutions are found.
The program is free of charge for academic and non-commercial use and can be downloaded in sourcecode via http://webhotel4.ruc.dk/~keld/research/LKH-3. A comprehensive library of test instances(about 10,000) and the best solutions obtained by LKH-3 for these instances can also be downloaded.
A comparison with the best known solutions are given in tables.

10References[1]

Helsgaun, K.:
An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic.
Eur. J. Oper. Res., 126(1):106-130 (2000)[2]

Helsgaun, K.:
General k-opt submoves for the Lin-Kernighan TSP heuristic.
Math. Prog. Comput., 1(2-3):119-163 (2009)[3]

Lin. S., Kernighan, B. W.:
An Effective Heuristic Algorithm for the Traveling-Salesman Problem.
Oper. Res. 21, 498-516 (1973)[4]

Bektas, T.:
The multiple traveling salesman problem: an overview of formulations and solution
procedures.
Omega, 34(3):209-219 (2006)[5]

Johnson D.S., Gutin G., McGeoch L.A., Yeo A., Zhang W., Zverovitch A.: Experimental
Analysis of Heuristics for the ATSP.
In: Gutin G., Punnen A.P. (eds.): The Traveling Salesman Problem and Its Variations.
Combinatorial Optimization, vol. 12. Springer, Boston, MA (2007)[6]

Rao, M. R.:
A note on the multiple traveling salesman problem.
Oper. Res., 28(3):628–32 (1980)[7]

Jonker, R., Volgenant, T.:
Technical Note - An Improved Transformation of the Symmetric Multiple Traveling Salesman
Problem.
Oper. Res., 36(1):163-167 (1988)[8]

Jonker, R., Volgenant, T.:
Transforming asymmetric into symmetric traveling salesman problems.
Oper. Res. Let., 2:161-163 (1983)[9]Fredman, M. L., Johnson, D. S., McGeoch, L. A.:
Data Structures for Traveling Salesmen.
J. Algorithms, 16:432-479 (1995)[10]

Reinelt, G.:
TSPLIB - A Traveling Salesman Problem Library.
ORSA J. Comput., 3(4):376-385 (1991)

11

Problem-specific literature

12

ACVRP: Asymmetric capacitated vehicle routing problem
Batsyn, M., Goldengorin, B., Kocheturov, A., Pardalos, P. M.:
Tolerance-Based vs. Cost-Based Branching for the Asymmetric Capacitated Vehicle Routing
Problem.
In: Proceedings of the Second International Conference on Network Analysis:1-10 (2013)
Fischetti, M., Toth, P., Vigo, D.,
A Branch-And-Bound Algorithm for the Capacitated Vehicle Routing Problem on Directed Graphs.
Oper. Res., 42(5):846-859 (1994)
Leggieri, V., Haouari, M.:
A matheuristic for the asymmetric capacitated vehicle routing problem.
Discrete Appl. Math., Available online 6 May (2016)
Vigo, D.:
A Heuristic Algorithm for the Asymmetric Capacitated Vehicle Routing Problem.
Eur. J. Oper. Res., 89(1):108-126 (1996)13

BWTSP: Black and white traveling salesman problem
Bhattacharya, B.., Hu, Y., Kononov, A.:
Approximation Algorithms for the Black and White Traveling Salesman Problem.
Lecture Notes in Computer Science, 4598:493-503 (2007)
Bourgeois, M., Laporte, G., Semet, F.:
Heuristics for the black and white traveling salesman problem.
Comput. Oper. Res., 30(1):75-85 (2003)
Ghiani, G., Laporte, G., Semet, F.:
The Black and White Traveling Salesman Problem.
Oper. Res., 54(2): 366-378 (2006)
Gouveia, L., Leitner, M., Ruthmair, M.:
Extended formulations and branch-and-cut algorithms for the Black-and-White Traveling Salesman
Problem.
Eur. J. Oper. Res., 262(3):908-928 (2017)
Li, H., Alidaee, B.:
Tabu search for solving the black-and-white travelling salesman problem.
J. Oper. Res. Soc., 67(8):1061-1078.
Muter, I.:
A new formulation and approach for the black and white traveling salesman problem.
Comput. Oper. Res., 53: 96-106 (2015)14

1-PDTSP: One-commodity pickup-and-delivery traveling salesman problem
Erdoğan G., Laporte, G., Calvo, R. W.:
The One Commodity Pickup and Delivery Traveling Salesman Problem with Demand Intervals.
CIRRELT 46 (2013)
Guerine, M., Rossetiand, I., Plastino, A.:
Extending the hybridization of metaheuristics with data mining: Dealing with sequences.
Intell. Data Anal., 20(5):1133-1156 (2016)
Hernández-Pérez, H., Salazar-González, J-J.:
A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery.
Discrete Appl. Math., 145(1):126-139 (2004)
Hernández-Pérez, H., Salazar-González, J-J.:
Heuristics for the One-Commodity Pickup-and-Delivery Traveling Salesman Problem.
Trans. Sci., 38(2):245-255 (2004)
Hernández-Pérez, H., Salazar-González, J-J.:
The One-commodity Pickup-and-Delivery Traveling Salesman Problem: Inequalities andAlgorithms.
Networks, 50(4):258-272 (2007).
Hernández-Pérez, H., Rodríguez-Martín, I., Salazar-González, J-J.:
A hybrid GRASP/VND heuristic for the One-Commodity Pickup-and-Delivery Traveling
Salesman Problem.
Comput. Oper. Res., 36(5):1639-1645 (2009)
Hosny, M. I., Mumford, C. L.:
Solving the One-Commodity Pickup and Delivery Problem Using an Adaptive Hybrid VNS/SAApproach.
J. Heu., 16 (3):417-439 (2010)
Luong, B. T.:
One commodity pickup and delivery traveling salesman problem and an extension
formulations and algorithms.
MSc thesis, Purdue University (2011)
Mladenovic N., Uroševic, D., Hanafi, S., Ilic A.:
A general variable neighborhood search for the one-commodity pickup-and-delivery travelling
salesman problem.
Eur. J. Oper. Res., 220(1):270-285 (2012)
Mosheiov, G.,
The travelling salesman problem with pick-up and delivery.
Eur. J. Oper. Res., 79(2):299-310 (1994)

15

Ren, L., Duhamel, C., Quilliot, A.:A hybrid ILS/VND heuristic for the One-Commodity Pickup-and-Delivery Traveling Salesman
Problem.
In: Proceedings of International Workshop on Green Supply Chain, GSC (2012).
Yahyaoui, H., Tlili, T., Krichen, S.:
A Randomized Multi-start Genetic Algorithm for the One-Commodity Pickup-and-Delivery
Traveling Salesman Problem.
In: Advances in Swarm and Computational Intelligence, LNCS 9142:4549 (2015)
F. Zhao, F., Li, S., Sun, J., Mei, D.:
Genetic algorithm for the one-commodity pickup-and-delivery traveling salesman problem.
Comput. Ind. Eng., 56(4):16421648 (2009)16

CCVRP: Cumulative capacitated vehicle routing problem
Ke, L., Feng, Z.:
A two-phase metaheuristic for the cumulative capacitated vehicle routing problem.
Comput. Oper. Res., 40(2):633-638 (2013)
Lysgaard, J., Wøhlk, S.:
A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem.
Eur. J. Oper. Res., 236(3):800-810 (2014)
Ngueveu, S. U., Prins, C., Calvo, R. W.:
An effective memetic algorithm for the cumulative capacitated vehicle routing problem.
Comput. Oper. Res., 37(11):1877-1885 (2010)
Ribeiro, M. R, Laporte, G.:
An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing
problem.
Comput. Oper. Res., 39(3):728-735 (2012)
Sze. J. F, Salhi, S, Wassan, N.:
The cumulative capacitated vehicle routing problem with min-sum and min-max objectives:
An effective hybridisation of adaptive variable neighbourhood search and largeneighbourhood search.
Transp. Res., Part B, 101:162-184 (2017)17

CVRP: Capacitated vehicle routing problem
Alba, E., Dorronsoro, B.:
A Hybrid Cellular Genetic Algorithm for the Capacitated Vehicle Routing Problem.
In: Engineering Evolutionary Intelligent Systems:379-422 (2008)
Augerat, P., Belenguer, J. M., Benavent, E., Corberin, A., Naddef, D.:
Separating capacity constraints in the CVRP using tabu search.
Eur. J. Oper. Res., 106(2-3):546-557 (1998)
Beasly, J E.:
Route first--Cluster second methods for vehicle routing.
Omega, 11(4):403-408 (1983)
Bjarnadóttir, A. S.:
Solving the Vehicle Routing Problem with Genetic Algorithms.
MSc thesis, Technical University of Denmark (2004)
Brajevic, I.:
Artificial bee colony algorithm for the capacitated vehicle routing problem.
In: Proceedings of the European Computing Conference 2011:239-244 (2011)
Bräysy, O.:
Fast Local Searches For The Vehicle Routing Problem With Time Windows.
INFOR, 40(4):319-330 (2002)
Breedam, A. V.:
An Analysis of the Behavior of Heuristics for the Vehicle Routing Problem for a selection ofproblems with Vehicle-related, Customer-related, and Time-related Constraints.
PhD thesis, University of Antwerp (1994)
Breedam, A. V.,
Comparing descent heuristics and metaheuristics for the vehicle routing problem.
Comput. Oper. Res., 28(4):289-315 (2001)
Breedam, A. V.:
A parametric analysis of heuristics for the vehicle routing problem with side-constraints.
Eur. J. Oper. Res., 137(2):348-370 (2002)
Chen, P., Huang, H., Dong, X.:
Iterated variable neighborhood descent algorithm for the capacitated vehicle routing problem.
Expert Syst. Appl., 37(2):1620-1627 (2010)
Christofides, N., Eilon, S.:
An algorithm for the vehicle-dispatching problem.
Oper. Res. Quart., 20:309–318 (1969)18

Christofides, N., Mingozzi, A., Toth, P.:
The vehicle routing problem.
In Christofides, N., Mingozzi, A., Toth, P., Sandi, C. (Eds.):
Combinatorial optimization: vol. 1, pp. 315–338, (1979).
Cordeau, J-F., Gendreau, M., Hertz, A., Laporte, G., Sormany, J-S.:
New Heuristics for the Vehicle Routing Problem.
In: Logistics Systems: Design and Optimization:279-297 (2004)
Dorronsoro, B., Aria, D., Luna, F., Nebro, A. J., Alba, E.:
A grid-based hybrid cellular genetic algorithm for very large scale instances of the CVRP.
In: Proceedings 21st European Conference on Modelling and Simulation:759-765 (2007)
Fan, Z., Tu, W., Li, Q., Shaw, S-L., Chen, S., Chen, B. Y.:
A Voronoi neighborhood-based search heuristic for distance/capacity constrained very large
vehicle routing problems.
Int. J. Geogr. Inf. Sci., 27(4):741-764 (2013)
Fischetti, M., Toth, P.:
A new ILP-based refinement heuristic for Vehicle Routing Problems.
Math. Prog., 105(2):471-499 (2006)
Fisher, M. L., Jaikumar, R.:
A generalized assignment heuristic for vehicle routing.
Networks, 11(3): 109-124 (1981)
Fosin, J., Caric, T., Ivanjko, E.:
Vehicle Routing Optimization Using Multiple Local Search Improvements.
Automatika, 55(2):124-132 (2014)
Frutos, M., Tohmé, F.:
A New Approach to the Optimization of the CVRP through Genetic Algorithms.
AJOR, 2(4):495-501 (2012)
Fukasawa, R., Longo, H., Lysgaard, J., Aragäo, M. P. de, Reis, M., Uchoa, E., Werneck, R.F.:
Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem.
Math. Prog., Ser. A, 106:491511 (2006)
Funke, B., Grünert, T., Irnich, S.:
Local Search for Vehicle Routing and Scheduling Problems: Review and Conceptual Integration.
J. Heu., 11(4):267306 (2005)
Gendreau, M., Hertz, A., Laporte, G.:
A Tabu Search Heuristic for the Vehicle Routing Problem.
Manage. Sci., 40(10):1276-1290 (1994)

19

Golden, B. L., Wasil, E. A., Kelly, J. P., Chao, I-M.:
The Impact of Metaheuristics on Solving the Vehicle Routing Problem: Algorithms, Problem Sets,
and Computational Results.
In: Fleet Management and Logistics (T. G. Crainic. T. G. Laporte, G., eds.).
Kluwer Academic, Boston, pp. 33–56 (1998)
Golden, B. L, Magnanti, T. L., Nguen, H. Q.:
Implementing vehicle routing algorithms.
Networks, 7(2):113-148 (1977)
Gröer, C.:
Parallel and serial algorithms for vehicle routing problems.
PhD thesis, University of Maryland (2008)
Gröer, C., Golden, B., Wasil, E.:
A library of local search heuristics for the vehicle routing problem.
Math. Prog. Comput., 2(2):79101 (2010)
Guimarans, D., Herrero, R., Riera, D., Juan, A. A., Ramos, J. J.:
Combining probabilistic algorithms, Constraint Programming and Lagrangian Relaxation to solve
the Vehicle Routing Problem.
Ann. Math. Artific. Intell., 62(3-4):299315 (2011)
Guimarans, D., Herrero, R., Riera, D., Juan, A.A, J. J. Ramos, J. J.:
Solving Vehicle Routing Problems Using Constraint Programming and Lagrangean Relaxation in a
Metaheuristics Framework.
IJISSCM, 4(2):61-81 (2011)
Hasle, G., Kloster, O.;
Industrial Vehicle Routing.
In: Geometric Modelling, Numerical Simulation, and Optimization: Applied Mathematics at
SINTEF (2007)
Irnich, S., Funke, B., Grünert, T.:
Sequential search and its application to vehicle-routing problems.
Comput. Oper. Res., 33(8):24052429 (2005)
Irnich, S.:
A Unified Modeling and Solution Framework for Vehicle Routing and Local Search-Based
Metaheuristics.
INFORMS J. Comput., 20(2):270-287 (2008)
Jin, J., Crainic, T. G., Løkketangen, A.:
A Cooperative Parallel Metaheuristic for the Capacitated Vehicle Routing Problem.
Comput. Oper. Res., 44:33-41 (2014)20

Juan, A. A., Faulin, J., Jorba, J., Barrios, B.:
SR-2: A Hybrid Algorithm for the Capacitated Vehicle Routing Problem.
Faculty Research & Creative Works, Paper 586 (2008)
Juan, A. A., Faulin, J., Ruiz, R., Barrios, B., Caballé, S.:
The SR-GCWS hybrid algorithm for solving the capacitated vehicle routing Problem.
Appl. Soft Comput., 10(1):215224 (2010)
Kindervater, G. A. P., Savelsbergh, M. W. P.:
Vehicle Routing 2: Handling Side Constraints.
Technical report, School of Industrial and Systems Eng., Georgia Institute of Tech. (1995)
Kubiak, M., Wesolek, P.:
Accelerating Local Search in a Memetic Algorithm for the Capacitated Vehicle Routing
Problem.
In: EvoCOP 2007:99-107, 2007.
Kytöjoki, J., Nuortio, T., Bräysy, O., Gendreau, M.:
An efficient variable neighborhood search heuristic for very large scale vehicle routing problems.
Comput. Oper. Res., 34(3):2743-2757 (2007)
Laporte, G.:
The Vehicle Routing Problem: An overview of exact and approximate algorithms.
Eur. J. Oper. Res., 59(3): 345-358 (1992)
Laporte, G., Gendreau, M., Potvin, J-Y., Semet, F.:
Classical and modern heuristics for the vehicle routing problem.
Int. T. Oper. Res., 7(4-5):285-300 (2000)
Layeb, A., Ammi, M., Chikhi, S.:
A GRASP Algorithm Based on New Randomized Heuristic for Vehicle Routing Problem.
J. Comput. Inf. Tech., Volume 21(1), pp. 35-46, 2013.
Li, F., Golden B., Wasil, E.:
Very large-scale vehicle routing: new test problems, algorithms, and results.
Comput. Oper. Res., 32(5):1165-1179 (2005)
Liu, W., Li, X.:
A Problem-Reduction Evolutionary Algorithm for Solving the Capacitated Vehicle Routing
Problem.
Math. Prob. Eng., Article ID 165476, 11 pages, 2015.
Marinakis, Y., Marinaki, M., Dounias, G.:
Honey Bees Mating Optimization algorithm for large scale vehicle routing problems.
Nat. Comput., 9(1):527 (2010)21

Naddef, D., Rinaldi, G.;
Branch and cut algorithms for the vehicle routing problem.
Istituto di analisi dei sistemi ed informatica, R. 515 (1999)
Nagata, Y., Bräysy, O.:
Edge Assembly-Based Memetic Algorithm for the Capacitated Vehicle Routing Problem.
Networks, 54(4):205-215 (2009)
Niu, Y., Wang, S., He, J., Xiao, X.:
A novel membrane algorithm for capacitated vehicle routing problem.
Soft Comput., 19(2):471482 (2015)
Pecin, D., Pessoa, A., Poggi, M., Uchoa, E.:
Improved branch-cut-and-price for capacitated vehicle routing.
Math. Prog. Comput., 9(1):61100 (2017)
Perboli, G., Pezzellam, F., R. Tadei, R.:
EVE-OPT: a hybrid algorithm for the capacitated vehicle routing problem.
Math. Method. Oper. Res., 68(2):361382 (2008)
Pessoa, A., Aragão, M. P. De, Uchoa, E.:
Robust Branch-Cut-and-Price Algorithms for Vehicle Routing Problems.
In: The vehicle routing problem: Latest advances and new challenges: 297-325 (2008)
Pisinger, D., Ropke, S.:
A general heuristic for vehicle routing problems.
Comput. Oper. Res., 34(8):2403-2435 (2005)
Pornsing, C.;
A particle swarm optimization for the vehicle routing problem with simultaneous pickup anddelivery.
Comput. Oper. Res., 36(5):1693-1702 (2009)
Qi, C.:
Vehicle Routing Optimization in Logistics Distribution using Hybrid Ant Colony Algorithm.
TELKOMNIKA, 11(9):5308~5315 (2013)
Qi, C., Li, P.:
An Exponential Entropy-based Hybrid Ant Colony Algorithm for Vehicle Routing Optimization.
Appl. Math. Inf. Sci., 8(6):3167-3173 (2014)
Qui, S.:
Airline crew pairing optimization problems and capacitated vehicle routing problems.
PhD thesis, Georgia Institute of Technology (2013)
Ralphs, T., Kopman, L., Pulleyblank, W., Trotter, L. E.:
On the Capacitated Vehicle Routing Problem.
Math. Prog., 94(2):343-359 (2003)

22

Roberti, R.:
Exact Algorithms for Different Classes of Vehicle Routing Problems.
PhD thesis, University of Bologna (2012)
Rochat, Y., Taillard, É. D.:
Probabilistic diversification and intensification in local search for vehicle routing.
J. Heur., 1(1): 147-167 (1995)
Ropke, S.:
Heuristic and exact algorithms for vehicle routing problems.
PhD thesis, Technical University of Denmark (2005)
S. Ropke,
Parallel large neighborhood search - a software framework.
The VIII Metaheuristics International Conference (2009)
Ruttanateerawichien, K., Kurutach, W.:
An Improved Golden Ball Algorithm for the Capacitated Vehicle Routing Problem.
In: Bio-Inspired Computing - Theories and Applications:341-356 (2014)
Shin, K., Han, S.:
A Centroid-based Heuristic Algorithm for the Capacitated Vehicle Routing Problem.
Comput. Inf., 30(4):721732 (2011)
Snoeys, C.:
Comparison of Meta-heuristic Approaches for Large-scale Vehicle Routing Problems.
MSc thesis, Ghent University (2014)
Subramanian, S.:
Heuristic, Exact and Hybrid Approaches for Vehicle Routing Problems.
PhD thesis, Universidade Federal Fluminense (2012)
Subramanian, A., Uchoa, E., Ochi, L.S.:
A hybrid algorithm for a class of vehicle routing problems.
Comput. Oper. Res., 40(10):2519-2531 (2013)
Sze, J., F., Salhi, S., Wassan, N.:A hybridisation of adaptive variable neighbourhood search and large neighbourhood search:
Application to the vehicle routing problem.
Expert Syst. Appl., 65:383-397 (2016)
Szeto, W.Y., Wu, Y., Ho, S. C.:
An artificial bee colony algorithm for the capacitated vehicle routing problem.
Eur. J. Oper. Res, 215(1):126135 (2011)
Takes, F. W., Kosters, W. A.:
Applying Monte Carlo Techniques to the Capacitated Vehicle Routing Problem.
22th Benelux Conference on Artificial Intelligence (2010)23

Teymourian, E., Kayvanfar, V., Komaki, GH. M., Zandieh, M.:
Enhanced Intelligent Water Drops and Cuckoo Search Algorithms for Solving the Capacitated
Vehicle Routing Problem.
Inf. Sci., 334-335:354-378 (2016)
Toth, P., Tramontani, A.:
An Integer Linear Programming Local Search for Capacitated Vehicle Routing Problems.
In: The Vehicle Routing Problem: Latest Advances and New Challenges: 275-295 (2008)
Toth, P., Vigo, D.:
The Granular Tabu Search and Its Application to the Vehicle-Routing Problem.
INFORMS J. Comput., 15(4):333-346 (2003)
Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Vidal, T., Subramanian, A.:
New Benchmark Instances for the Capacitated Vehicle Routing Problem.
Eur. J. Oper. Research, 257(3):845-858 (2017)
Vigo, D.:
A Heuristic Algorithm for the Asymmetric Capacitated Vehicle Routing Problem.
Eur. J. Oper. Res., 89(1):108-126 (1996)
Volna, E., Kotyrba,M.:
Unconventional Heuristics for Vehicle Routing Problems.
J. Numer. Anal., Industrial and Applied Mathematics, 9-10(3-4):57-67 (2016)
Yousefikhoshbakht, Y., Khorram, E.:
Solving the vehicle routing problem by a hybrid meta-heuristic algorithm.
J. Ind. Eng. Int, 8(1), 11 pages, 2012.
Zachariadis, E. E., Kiranoudis, C. T.:
A Strategy for Reducing the Computational Complexity of Local Search-Based Methods, and its
Application to the Vehicle Routing Problem.
Comput. Oper. Res., 37(12):2089-2105 (2010)
Zhou, Y., J. Xie, J., Zheng, H.;
A Hybrid Bat Algorithm with Path Relinking for Capacitated Vehicle Routing Problem.
Math. Prob. Eng., Article ID 392789, 10 pages (2013)24

CVRPTW: Capacitated vehicle routing problem with time windows
Alvarenga, G. B., Mateus, G. R., Tomi, G. De:
Finding Near Optimal Solutions for Vehicle Routing Problems with Time Windows Using Hybrid
Genetic Algorithm.
In: Proceedings of the Second International Workshop on Freight Transportation and Logistics(2003)
Bräysy, O., Gendreau, M.:
Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search
Algorithms.
Transp. Sci., 39(1):104-118 (2005)
Bräysy, O., Gendreau, M.:
Vehicle Routing Problem with Time Windows, Part II: Metaheuristics.
Transp. Sci., 39(1):119-139 (2005)
Cordeau, J-F., Desaulniers, G., Desrosiers, J., Solomon, M. M., Soumis, S.:
VRP with Time Windows.
In: The Vehicle Routing Problem:157-193 (2001)
Figliozzi, M.A.:
An Iterative Route Construction and Improvement Algorithm for the Vehicle Routing Problem with
Soft and Hard Time Windows.
Transp. Res., Part C, Emerging Technologies, 18(5):668-679 (2010).
Gambardella, L. M., Taillard, E., Aggazzi, G.:
MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows.
Technical report, Istituto Dalle Molle Di Studi Sull Intelligenza Artificiale (1999)
Gehring, H., Homberger, J.:
A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows.
In: Proceedings of EUROGEN99:57–64 (1999)
Gendreau, M., Tarantilis, C. D.:
Solving Large-Scale Vehicle Routing Problems with Time Windows: The State-of-the-Art.
CIRRELT-2010-04 (2010)
Jepsen, M., Spoorendonk, S., Petersen, B., Pisinger, D.,
A Non-Robust Branch-And-Cut-And-Price Algorithm for the Vehicle Routing Problem with Time
Windows.
Technical Report no. 06/03, DIKU, University of Copenhagen (2003)
Jepsen, M.:
Branch-and-cut and Branch-and-Cut-and-Price Algorithms for Solving Vehicle Routing Problems.
PhD thesis, Technical University of Denmark (2011)25

Kallehauge, B.:
On the vehicle routing problem with time windows.
PhD thesis, Technical University of Denmark (2006)
Kisjes, K.;
A Quantitative Comparison of Generalized Fast Construction Heuristics for the Vehicle Routing
Problem with Time Windows.
MSc thesis, Erasmus University Rotterdam (2012)
Kohl, N., Madsen, O. B. G.:
An Optimization Algorithm for the Vehicle Routing Problem with Time Windows Based on
Lagrangian Relaxation.
Oper. Res., 45(3):395-406 (1997)
Larsen, J.;
Vehicle Routing with Time Windows - Finding optimal solutions efficiently.
Technical report, Technical University of Denmark (1999)
Larsen, J.:
Parallelization of the Vehicle Routing Problem with Time Windows.
PhD thesis, Technical University of Denmark (2001)
Larsen, J.;
Speeding up the solution process for the Vehicle Routing Problem with Time Windows using
structural information.
Technical report, Technical University of Denmark (2001)
Lau, H. C., Sim, M., Teo, K M.;
Vehicle routing problem with time windows and a limited number of vehicles.
Eur. J. Oper. Res., 148(3):559569 (2003)
Lysgaard, J.:
Reachability Cuts for the Vehicle Routing Problem with Time Windows.
Eur. J. Oper. Res., 175(1):210-223 (2006)
Mester, D, Bräysy, O.:
Active guided evolution strategies for large-scale vehicle routing problems with time windows.
Comput. Oper. Res., 32(6):15931614 (2005)
Minocha, B., Mohan, C.:
Solution of VRPTW using controlled random search technique.
In: Proceedings of the 3rd International Conference on Electronics: 203-208 (2011)
Nalepa, J., Czech, Z. J.:
A Parallel Memetic Algorithm to Solve the Vehicle Routing Problem with Time Windows.
Studia Informatica, 33(1): 91106 (2012)26

Razavi, M., Eshlaghy, A. T.:
Using an Ant Colony approach for Solving capacitated Vehicle Routing Problem with time
Windows.
R. J. Recent Sci., 4(2): 30-35 (2015)
Russell, R.:
Hybrid Heuristics for the Vehicle Routing Problem with Time Windows.
Transp. Sci., 29: 156-166 (1995)
Schulze, J., Fahle, T.:
A parallel algorithm for the vehicle routing problem with time window constraints.
Ann. Oper. Res., 86(0):585-607 (1999)

27

DCVRP: Distance constrained capacitated vehicle routing problem
Almoustafa, S.:
Distance-constrained vehicle routing problem: exact and approximate solution (mathematicalprogramming).
PhD thesis, Brunel University (2013)
Almoustafa, S., Hanafi, S., Mladenović, N.:
New exact method for large asymmetric distance-constrained vehicle routing problem.
Eur. J. Oper. Res., 226(3):386-394 (2013)
Laporte, G., Desrochers, M., Nobert, Y.:
Two exact algorithms for the distance-constrained vehicle routing problem.
Networks, 14(1):161-172 (1984)
Laporte, G., Nobert, Y., Tailefer, S.:
A branch-and-bound algorithm for the asymmetrical distance-constrained vehicle routing problem.
Math. Model., 9(12):857-868 (1987)
Viswanath N., Ravi, R.:
Approximation algorithms for distance constrained vehicle routing problems.
Networks, 59(2):209-214 (2012)
Tlili, T., Faiz, Krichen, S.:
A Hybrid Metaheuristic for the Distance-constrained Capacitated Vehicle Routing Problem.
Procedia - Soc. Beh. Sci., 109:779-783 (2014)28

1-PDTSP: One-commodity pickup-and-delivery traveling salesman problem
Erdoğan G., Laporte, G., Calvo, R. W.:
The One Commodity Pickup and Delivery Traveling Salesman Problem with Demand Intervals.
CIRRELT 46 (2013)
Guerine, M., Rossetiand, I., Plastino, A.:
Extending the Hybridization of Metaheuristics with Data Mining to a Broader Domain.
In: Proceedings of the 16th International Conference on Enterprise Information Systems, ICEIS:
395-406 (2014)
Guerine, M., Rossetiand, I., Plastino, A.:
Extending the hybridization of metaheuristics with data mining: Dealing with sequences.
Intell. Data Anal., 20(5):1133-1156 (2016)
Hernández-Pérez, H., Salazar-González, J-J.:
A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery.
Discrete Appl. Math., 145(1):126-139 (2004)
Hernández-Pérez, H., Salazar-González, J-J.:
Heuristics for the One-Commodity Pickup-and-Delivery Traveling Salesman Problem.
Trans. Sci., 38(2):245-255 (2004)
Hernández-Pérez, H., Salazar-González, J-J.:
The One-commodity Pickup-and-Delivery Traveling Salesman Problem: Inequalities andAlgorithms.
Networks, 50(4):258-272 (2007).
Hernández-Pérez, H., Rodríguez-Martín, I., Salazar-González, J-J.:
A hybrid GRASP/VND heuristic for the One-Commodity Pickup-and-Delivery Traveling
Salesman Problem.
Comput. Oper. Res., 36(5):1639-1645 (2009)
Hosny, M. I., Mumford, C. L.:
Solving the One-Commodity Pickup and Delivery Problem Using an Adaptive Hybrid VNS/SAApproach.
J. Heu., 16 (3):417-439 (2010)
Luong, B. T.:
One commodity pickup and delivery traveling salesman problem and an extension
formulations and algorithms.
MSc thesis, Purdue University (2011)
Mladenovic N., Uroševic, D., Hanafi, S., Ilic A.:
A general variable neighborhood search for the one-commodity pickup-and-delivery travelling
salesman problem.
Eur. J. Oper. Res., 220(1):270-285 (2012)29

Ren, L., Duhamel, C., Quilliot, A.:A hybrid ILS/VND heuristic for the One-Commodity Pickup-and-Delivery Traveling Salesman
Problem.
In: Proceedings of International Workshop on Green Supply Chain, GSC (2012).
Yahyaoui, H., Tlili, T., Krichen, S.:
A Randomized Multi-start Genetic Algorithm for the One-Commodity Pickup-and-Delivery
Traveling Salesman Problem.
In: Advances in Swarm and Computational Intelligence, LNCS 9142:4549 (2015)
F. Zhao, F., Li, S., Sun, J., Mei, D.:
Genetic algorithm for the one-commodity pickup-and-delivery traveling salesman problem.
Comput. Ind. Eng., 56(4):16421648 (2009)30

m-PDTSP: Multi-commodity pickup-and-delivery traveling salesman problem
Eskildsen, C. B.:
A meta-heuristic for the multi-commodity Pickup-and-Delivery Traveling Salesman Problem.
MSc thesis, Aarhus University (2015)
Hernandez-Pérez, H., Rodríguez-Martín, I., Salazar-González, J-J.:
A hybrid heuristic approach for the multi-commodity pickup-and-delivery traveling salesman
problem.
Eur. J. Oper. Res., 251(1):44-52 (2016)
Hernandez-Pérez, H., Salazar-González, J-J.:
The Multi-commodity Pickup-and-Delivery Traveling Salesman Problem.
Networks, 63(1):46-59 (2014)31

m1-PDTSP: Multi-commodity one-to-one pickup-and-delivery traveling salesman problem
Hernandez-Pérez, H., Salazar-González, J-J.:
The multi-commodity one-to-one pickup-and-delivery traveling salesman problem.
Eur. J. Oper. Res., 196(3): 987-995 (2009)32

MTRP: Multiple traveling repairman problem
Onder, G.:
New formulations for multiple traveler minimum latency problem. [in Turkish]
Thesis, Baskent University (2015)
Onder, G., Kara, I., Derya, T.:

New integer programming formulation for multiple traveling repairmen problem.
Transp, Res. Proc., 22:355–361 (2017)33

MTRPD: Multiple traveling repairman problem with distance constraints
Luo, Z., Qin, H., Lim, A.:
Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints.
Eur. J. Oper. Res., 234(1):49-60 (2014)34

mTSP: Multiple traveling salesmen problem
Applegate, D., Cook, W., Dash, S.; Rohe, A.:
Solution of a min-max vehicle routing problem.
INFORMS J. Comput., 14(2):132-143 (2002)
Baranwal, M., Roehl, B., Salapaka, S. M.:
A Deterministic Annealing Approach to the Multiple Traveling Salesmen and Related Problems.
arXiv:1604.04169 (2016)
Bektas, T.,
The multiple traveling salesman problem: an overview of formulations and solution procedures.
Omega, 34(3):209-219 (2004)
Bolaños, R. I., Toro, E. M. O., Granada, M. E.:
A population-based algorithm for the multi travelling salesman problem.
Int. Ind. Eng. Comput., 7(2):245-256 (2016)
Carter, E.,
Design and Application of Genetic Algorithms for the Multiple Traveling Salesperson Assignment
Problem.
PhD thesis, Virginia Polytechnic Institute and State University (2003)
Carter E., and Ragsdale, C.:
A new approach to solving the multiple traveling salesperson problem using genetic algorithms.
Eur. J. Oper. Res., 175(1):246-257 (2006)
Chen, S. H.:
Minimization of the Total Traveling Distance and Maximum Distance by Using a TransformedBased Encoding EDA to Solve the Multiple Traveling Salesmen Problem.
Math. Prob. Eng., Article ID 640231, 13 pages (2015)
Cornu, M., Cazenave, T., Vanderpooten, D.:
Perturbed Decomposition Algorithm applied to the multi-objective Traveling Salesman Problem.
Comput. Oper. Res., 79:314-330 (2017)
França, P.M., Gendreau, M., Laporte, G., Müller, F.:
The m-Traveling Salesman Problem with Minimax Objective.
Transp. Sci., 29(3):267-275 (1995)
Gavish, B., Srikanth, K.:
An Optimal Solution Method for Large-Scale Multiple Traveling Salesmen Problems.
Oper. Res., 34(5):698-717 (1986)
Golden, B. L., Laporte, G., Taillard, É. D.:
An Adaptive Memory Heuristic for a Class of Vehicle Routing Problems with Minmax Objective.
Comput. Oper. Res., 24(5):445-452 (1997)

35

GuoXing, Y.:
Transformation of Multi-Depot Multi-Salesmen Problem to the standard Traveling Salesman
Problem.
Eur. J. Oper. Res., 81(3):557-560 (1995)
Hingrajiya, K. H., Gupta, R. K., Chandel, G. S.:
An Approach for Solving Multiple Travelling Salesman Problem using Ant Colony Optimization.
Comput. Eng. Intell. Syst., 6(2)13-17 (2015)
Hong S., Padberg, M. W.:
Technical Note - A Note on the Symmetric Multiple Traveling Salesman Problem with Fixed
Charges.
Oper. Res., 2(5):871-874 (1977)
Hosseinabadi, A. A. R., Kardgar, M., Shojafar, M., Shamshirband, S., Abraham A.:
GELS-GA: Hybrid Metaheuristic Algorithm for Solving Multiple Travelling Salesman Problem.
ISDA14’:76-81 (2014)
Jonker, R., Volgenant, T.:
Technical Note - An Improved Transformation of the Symmetric Multiple Traveling Salesman
Problem.
Oper. Res., 36(1):163-167 (1988)
Junjie, P., Dingwei, W.:
An Ant Colony Optimization Algorithm for Multiple Travelling Salesman Problem.
ICICIC’06, 4 pages (2006)
Kara, I., Bektas, T.:
Integer linear programming formulations of multiple salesman problems and its variations.
Eur. J. Oper. Res., 174(3):1449-1458 (2006)
Király, A., Abonyi, J.:
Optimization of Multiple Traveling Salesmen Problem by a Novel Representation based Genetic
Algorithm.
Intell. Comput. Optim. Eng., 366:241-269 (2011)
Kivelevitch, E., Cohen, K., Kumar, M.:
A Market-based Solution to the Multiple Traveling Salesmen Problem.
J. Intell. Rob. Syst., 72(1):21-40 (2013)
Kota, L., Jarmai, K.:
Mathematical modeling of multiple tour multiple traveling salesman problem using evolutionary
programming.
Appl. Math. Mod., 39(12):3410-3433 (2015)
Larki, H., Yousefikhoshbakht, M.:
Solving the Multiple Traveling Salesman Problem by a Novel Metaheuristic Algorithm.
J. Optim. Ind. Eng., 7(16): 55-63 (2014)36

Latah, M.:
Solving Multiple TSP Problem by K-Means and Crossover based Modified ACO Algorithm.
Int. J. Eng. Res. Tech., 5(2):430-434 (2016)
Masutti, T. A. S., Castro, L. N. De:
Neuro-immune approach to solve routing problems.
Neurocomputing, 72(10-12):2189-2197 (2009)
Mohammadpour, T., Yadollahi, M.:
Solving the Problem of Multiple Travelling Salesman Problem Using Hybrid Gravitational
Algorithm.
Int. J. Comm., 3:32-37 (2014)
Necula, R., Breaban, M., Raschip, M.:
Performance Evaluation of Ant Colony Systems for the Single-Depot Multiple Traveling Salesman
Problem.
International Conference on Hybrid Artificial Intelligence Systems:257-268 (2015)
Necula, R., Breaban, M., Raschip, M.:
Tackling the Bi-criteria Facet of Multiple Traveling Salesman Problem with Ant Colony Systems.
IEEE 27th International Conference on Tools with Artificial Intelligence:873-882 (2015)
Rostam, A. S., Mohanna, F., Keshavarz, H., Hosseinabadi, A. A. R.;
Solving Multiple Traveling Salesman Problem using the Gravitational Emulation Local Search
Algorithm.
Appl. Math. Inf. Sci., 9(2):1-11 (2015)
Russell, R. A.;
Technical Note - An Effective Heuristic for the M-Tour Traveling Salesman Problem with SomeSide Conditions.
Oper. Res., 25(3):517-524 (1977)
Salas, Y. J. C., Ledón, R. A., Machado, N. I. C., Nowé, A.:
Multi-type ant colony system for solving the multiple traveling salesman problem.
Revista Tecnica de la Facultad de Ingenieria Universidad del Zulia, 35(3): 311-320 (2012)
Sarin, S. C., Sherali, H. D., Judd, J. D., Tsai, P-F.,
Multiple asymmetric traveling salesmen problem with and without precedence constraints:
Performance comparison of alternative formulations .
Comput. Oper. Res., 51: 64-89 (2014)
Sedighpour, M., Yousefikhoshbakht, M., Darani, N. M.:
An Effective Genetic Algorithm for Solving the Multiple Traveling Salesman Problem.
J. Opt. Ind. Eng., 8:73-79 (2011)
Singh, A., Baghel, A. S.:
A new grouping genetic algorithm approach to the multiple traveling salesperson problem.
Soft Comput., 13(1):95-101 (2009)37

Singh, A.:
A Review on Algorithms Used to Solve Multiple Travelling Salesman Problem.
Int. Res. J. Eng. Tech., 3(4):598-603 (2016)
Somhom, S., Modares, A., Enkawa, T.:
Competition-based neural network for the multiple travelling salesmen problem with minmax
objective’.
Comput. Oper. Res., 26(4):395-407 (1999)
Soylu, B.:
A general variable neighborhood search heuristic for multiple traveling salesmen problem.
Comput. Ind. Eng., 90: 390-401 (2015)
P. Venkatesh, P., Singh, A.:
Two metaheuristic approaches for the multiple traveling salesperson problem.
Appl. Soft Comput., 26:74-89 (2015)
Wacholder, E., Han J., Mann, R. C.:A Neural Network Algorithm for the Multiple Traveling Salesmen Problem.
Biol. Cybern., 61(1):11-19 (1989)
Wang, Y., Chen, Y., Lin, Y.:
Memetic algorithm based on sequential variable neighborhood descent for the minmax multiple
traveling salesman problem.
Comput. Ind. Eng., 106:105-122 (2017)
Yousefikhoshbakht, M., Sedighpour, M.:
A combination of sweep algorithm and elite ant colony optimization for solving the multiple
traveling salesman problem.
Proceedings of the Romanian Academy - Series A, 13(4):295-301 (2012)
Yousefikhoshbakht, M., Didehvar, F., Rahmati, F.:
Modification of the Ant Colony Optimization for Solving the Multiple Traveling Salesman Problem.
Romanian Journal of Information Science and Technology, 16(1):65-80 (2013)
Yu Q., Wang, D., Lin, D., Li, Y., Wu, C.:A Novel Two-Level Hybrid Algorithm for Multiple Traveling Salesman Problems.
International Conference in Swarm Intelligence:497-503 (2012)
Yuan, Y., Skinner, B., Huang, S., Liu, D.:
A new crossover approach for solving the multiple travelling salesmen problem using genetic
algorithms.
Eur. J. Oper. Res., 228(1):72-82 (2013)
Zhou, H., Wei, Y.:
Optimization of Minimum Completion Time MTSP Based on the Improved DE.
Proceedings of the First international conference on Advances in Swarm Intelligence Volume Part I:489-498 (2010)38

OVRP: Open vehicle routing problem
Fleszar, K., Osman, I. H., Hindi, K. S.:
A variable neighbourhood search algorithm for the open vehicle routing problem.
Eur. J. Oper. Res., 195(3):803-809 (2009)
Li, F., Golden, B., Wasil, E.:
The open vehicle routing problem: Algorithms, large-scale test problems, and computational
results.
Comput. Oper. Res., 34(10):2918-2930 (2007)
Repoussis, P. P., Tarantilis, C. D., Bräysy, O., Ioannou, G.:A hybrid evolution strategy for the open vehicle routing problem.
Comput. Oper. Res., 37(3):443-455 (2010)
Salari, M., Toth, P., Tramontani, A.:
An ILP improvement procedure for the Open Vehicle Routing Problem .
Comput. Oper. Res., 37(12):2106-2120 (2010)
Subramanian, S.:
Heuristic, Exact and Hybrid Approaches for Vehicle Routing Problems.
PhD thesis, Universidade Federal Fluminense (2012)
Subramanian, A., Uchoa, E., Ochi, L.S.:
A hybrid algorithm for a class of vehicle routing problems.
Comput. Oper. Res., 40(10):2519-2531 (2013)
Zachariadis, E. E., Kiranoudis, C. T.:
An open vehicle routing problem metaheuristic for examining wide solution neighborhoods.
Comput. Oper. Res., 37(4):712-723 (2010)

39

PDPTW: Pickup-and-delivery problem with time windows
Bartolini, E.:
Algorithms for Network Design and Routing Problems.
PhD thesis, University of Bologna (2009)
Baldacci, R., Bartolini, E., Mingozzi, A.:
An Exact Algorithm for the Pickup and Delivery Problem with Time Windows.
Oper. Res., 59(2):414-426 (2011)
Bent, R., Hentenryck, P. Van:
A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows.
Comput. Oper. Res., 33(4):875-893 (2006)
Bettinelli, A.:
Mathematical Programming Algorithms for Transportation Problems.
PhD thesis, University of Milano (2009)

Furtado, M. G. S., Munari P., Morabito, R.:
Pickup and delivery problem with time windows: a new compact two-index formulation.
Oper. Res. Lett., 45(4):334-341 (2017)
Ganesh, K., Narendran, T. T.:
CLOVES: A cluster-and-search heuristic to solve the vehicle routing problem with delivery andpick-up.
Eur. J. Oper. Res., 178(3):699-717 (2007)
Hosny, M. I., Mumford, C. L.:
The Single Vehicle Pickup and Delivery Problem with Time Windows: Intelligent Operators for
Heuristic and Metaheuristic Algorithms.
J. Heu., 16(3):417-439 (2010)
Hosny, M. I., Mumford, C. L.:
Constructing initial solutions for the multiple vehicle pickup and delivery problem with time
windows.
Journal of King Saud University - Computer and Information Sciences, 24(1): 59-69 (2012)
Kalina; P., Vokínek, J.:
Parallel Solver for Vehicle Routing and Pickup and Delivery Problems with Time Windows Basedon Agent Negotiation.
IEEE International Conference on Systems, Man, and Cybernetics, 6 pages (2012)
Li, H., Lim, A.:
A Metaheuristic for the Pickup and Delivery Problem with Time Windows.
Int. J. Art. Tools, 12(2):173-186 (2003).

40

Lu, Q., Dessouky, M. M.:
A New Insertion-based Construction Heuristic for Solving the Pickup and Delivery Problem withTime Windows.
Eur. J. Oper. Res., 175(2):672-687 (2005)
Nanry, W. P., Barnes, J. W.:
Solving the pickup and delivery problem with time windows using reactive tabu search.
Transp. Res., Part B, 34(2):107-121 (2000)
Ropke, S., Pisinger, D.:
An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time
Windows.
Transp. Sci., 40(4):455-472 (2006)
Ropke, S., Cordeau, J-F.:
Branch-and-Cut-and-Price for the Pickup and Delivery Problem with Time Windows.
Transp. Sci., 43(3):267-286 (2009)41

PDTSP: Pickup-and-delivery traveling salesman problem
Dumitrescu, I., Ropke, S, Cordeau, J.-F., Laporte, G.:
The traveling salesman problem with pickup and delivery: polyhedral results and a branch-andcut algorithm.
Math. Prog., 121(1):269-305 (2010)
Gendreau, M., Laporte, G., Vigo, D.:
Heuristics for the traveling salesman problem with pickup and delivery.
Comput. Oper. Res., 26(7):699-714 (1999)
Renaud, J., Boctor, F. F., Ouenniche, J.:
A heuristic for the pickup and delivery traveling salesman problem.
Comput. Oper. Res., 27(9):905-916 (2000)
Renaud, J., Boctor, F. F., Laporte, G.:
Perturbation heuristics for the pickup and delivery traveling salesman problem.
Comput. Oper. Res., 29(9):1129-1141 (2002)

42

PDTSPF: Pickup-and-delivery traveling salesman problem with FIFO loadingErdoğan, G., Cordeau, J-F., Laporte, G.:
The pickup and delivery traveling salesman problem with first-in-first-out loading.
Comput. Oper. Res., 36(6):1800-1808 (2009)
Wei, L, Qin, H., Zhu, W., Wan, L.:
A study of perturbation operators for the pickup and delivery traveling salesman problem with
LIFO or FIFO loading.
J. Heu., 21(5):617-639 (2015)43

PDTSPL: Pickup-and-delivery traveling salesman problem with LIFO loading
Carrabs, F., Cordeau, J-F., Laporte, G.:
Variable Neighborhood Search for the Pickup and Delivery Traveling Salesman Problem with
LIFO Loading.
INFORMS J. Comput., 19(4):618-632 (2007)
Cheang, B., Gao, X., Lim, A., Qin, H., Zhu, W.:
Multiple pickup and delivery traveling salesman problem with last-in-first-out loading and distanceconstraints.
Eur. J. Oper. Res., 223(1):60-75 (2012)
Li, Y., Lim, A., Oon, W-C., Qin, H., Tu, D.:
The tree representation for the pickup and delivery traveling salesman problem with LIFO loading.
Comput. Oper. Res., 212(3):482-496 (2011)
Wei, L, Qin, H., Zhu, W., Wan, L.:
A study of perturbation operators for the pickup and delivery traveling salesman problem with
LIFO or FIFO loading.
J. Heu., 21(5):617-639 (2015)

44

RCTVRP: Risk-constrained cash-in-transit vehicle routing problem
Talarico, L.:
Secure Vehicle Routing: models and algorithms to increase security and reduce costs inthe cash-in-transit sector.
PhD thesis, Universiteit Antwerpen (2015)
Talarico, L., Sörensen, K., Springael, J.:
Metaheuristics for the risk-constrained cash-in-transit vehicle routing problem.
Eur. J. Oper. Res., 144(3):457470 (2015)
Talarico, L., Springael, J., Sörensen, K., Talarico, F.:
A large neighbourhood metaheuristic for the risk-constrained cash-in-transit vehicle routing
problem.
Comput. Oper. Res., 78:547-556 (2017)45

RCTVRPTW: Risk-constrained cash-in-transit vehicle routing with time windows
Talarico, L., Sörensen, K., Springael, J.:
The risk-constrained cash-in-transit vehicle routing problem with time window.
Research paper, University of Antwerp (2013)
Talarico, L.:
Secure Vehicle Routing: models and algorithms to increase security and reduce costs inthe cash-in-transit sector.
PhD thesis, Universiteit Antwerpen (2015)46

SOP: Sequential ordering problem
Anghinolfi, D., Montemanni, R., Paolucci, M., Gambardella, L. M.:
A hybrid particle swarm optimization approach for the sequential ordering problem.
Comput. Oper. Res., 38(7):1076-1085 (2011)
Ascheuer, N., Jünger, M., Reinelt, G.:
A Branch & Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence
Constraints.
Comput. Optim. Appl., 17(1):61-71 (2000)
Ezzat, A., Abdelbar, A. M., Wunsch II, D. C.:
A bare-bones ant colony optimization algorithm that performs competitively on the sequential
ordering problem.
Mem. Comput., 6(1):19-29 (2014)
Gambardella, L. M., Dorigo, M.:
An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem.
INFORMS J. Comput., 12(3):237-255 (2000)
Gambardella, L. M., Montemanni, R., Weyland, D.:
An Enhanced Ant Colony System for the Sequential Ordering Problem.
Oper. Res. Proc. 2011:355-360 (2012)
Gambardella, L. M., Montemanni, R., Weyland, D.:
Coupling ant colony systems with strong local searches.
Eur. J. Oper. Res., 220(3):831-843 (2012)
Gambardella, L. M.:
Coupling Ant Colony System with Local Search.
PhD thesis, IRIDIA, Université Libre de Bruxelles (2015)
Gouveia, L., Ruthmair, M.:
Load-Dependent and Precedence-Based Models for Pickup and Delivery Problems.
Comput. Oper. Res., 63:56-71 (2015)
Guerriero, F., Mancini, M.:
A cooperative parallel rollout algorithm for the sequential ordering problem.
Par. Comput. 29(5):663-677 (2003)
Montemanni, R., Smith, D. H., Gambardella, L. M.:
A Heuristic Manipulation Technique for the Sequential Ordering Problem.
Comput. Oper. Res., 35(12):3931-3944 (2008)
Montemanni, R., Mojana, Caro, M., A. Di, Gambardella, L. M.:
A decomposition-based exact approach for the sequential ordering problem.
J. Appl. Oper. Res., 5(1):2-13 (2013)47

Moon, C., Kim, J., Choi, G., Seo, Y.:An efficient genetic algorithm for the traveling salesman problem with precedence constraints.
Eur. J. Oper. Res., 140(3):606-617 (2002)
Nikolakopoulos, A., Sarimveis, H.:
A threshold accepting heuristic with intense local search for the solution of special instances of thetraveling salesman problem.
Eur. J. Oper. Res., 177(3):1911-1929 (2007)
Papapanagiotou, V., Jamal, J., Montemanni, R., Shobaki, G., Gambardella, L. M.:
A comparison of two exact algorithms for the sequential ordering problem.
Technical Report No. IDSIA-12-15, IDSIA / USI-SUPSI (2015)
Psaraftis, H. N.:
k-Interchange procedures for local search in a precedence-constrained routing problem.
Eur. J. Oper. Res., 13(4):391-402 (1983)
Seo, D-I., Moon, B-R.:
A Hybrid Genetic Algorithm Based on Complete Graph Representation for the Sequential Ordering
Problem.
GECCO 2003, LNCS 2723:669-680 (2003)
Shobaki, G., Jamal, J.:
An exact algorithm for the sequential ordering problem and its application to switching energy
minimization in compilers.
Comput. Optim. Appl., 61(2):343-372 (2015)
Skinderowicz, R.:
Population-Based Ant Colony Optimization for Sequential Ordering Problem.
ICCCI 2015, Part II, LNCS 9330:99-109 (2015)
Skinderowicz, R.:
An improved Ant Colony System for the Sequential Ordering Problem’.
Comput. Oper. Res., 86:1-17 (2017)
Sung, J, Jeong, B.:
An Adaptive Evolutionary Algorithm for Traveling Salesman Problem with Precedence
Constraints.
Scientific World J., Article ID 313767, 11 pages (2014)48

TRP: Traveling repairman problem
Blum, A. Chalasani, P., Coppersmith, D., Pulleyblank, B., Raghavan, P., Sudan, M.:
The Minimum Latency Problem.
STOC ’94:163-171 (1994)
Salehipour, A., Sörensen, K., Goos, P., Bräysy, O.:
Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem.
4OR-Q. J. Oper. Res, 9:189–209 (2011)
Silva M. M., Subramanian, A., Vidal T., Ochi, L. S.:
A simple and effective metaheuristic for the Minimum Latency Problem.
Eur. J. Oper. Res., 221(3):513-520 (2012)
Wu, B. Y., Huang, Z-N., Zhan, F-J.:
Exact algorithms for the minimum latency problem.
Inf. Proc. Lett., 92(6): 303-309 (2004)

49

TSPPD: Traveling salesman problem with pickups and deliveries
Mosheiov, G.:
The travelling salesman problem with pickup and delivery.
Eur. J. Oper. Res., 79:299-310 (1994)

50

TSPTW: Traveling salesman problem with time windows
Ascheuer, N., Fischetti, M., Grötschel, M.:
Solving the Asymmetric Travelling Salesman Problem with time windows by branch-and-cut.
Math. Prog., Ser. A 90:475-506 (2001)
Baldacci, R., Mingozzi, A., Roberti, R.:
New State-Space Relaxations for Solving the Traveling Salesman Problem with Time Windows.
INFORMS J. Comput., 24(3):356-371 (2012)
Calvo, R. W.:
A New Heuristic for the Traveling Salesman Problem with Time Windows.
Transp. Sci, INFORMS, 34(1):113-124 (2000)
Dash, S., Günlük, O., Lodi, A., Tramontani, A.:
A Time Bucket Formulation for the TSP with Time Windows.
INFORMS J. Comput., 24(1):132-147 (2010)
Dumas, Y., Desrosiers, Gelinas, J. E., Solomon, M. M.:
An Optimal Algorithm for the Traveling Salesman Problem with Time Windows.
Oper. Res., 43(2):367-371 (1995)
Edelkamp, S., Gath, M., Cazenavey, T., Teytaud, F.:
Algorithm and Knowledge Engineering for the TSPTW Problem.
2013 IEEE Symposium on Computational Intelligence in Scheduling, 8 pages (2013)
Favaretto, D., Moretti, E., Pellegrini, P.:
Ant Colony System for variants of Traveling Salesman Problem with Time Windows.
Technical Report, Ca'Foscari University of Venice, No. 120/2004 (2004)
Focacci, F., Lodi, A., Milano, M.:
A Hybrid Exact Algorithm for the TSPTW.
INFORMS J. Comput., 14(4):403-417 (2002)
Gendreau, M., A. Hertz, Laporte, G., Stan, M.:
A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows.
Oper. Res., 46(3):330-335 (1998)
Langevin, A., Desrochers, M., Desrosiers, J., Gélinas, S., Soumis, F.:
A two-commodity flow formulation for the travelling salesman and makespan problems with time
windows.
Networks, 23:631-640 (1993)
Li, J-Q.:
A Computational Study of Bi-directional Dynamic Programming for the Traveling Salesman
Problem with Time Windows.
Technical report, Working paper, University of California, Berkeley (2009)51

López-Ibáñez, M., Blum, C., Thiruvady, D., Ernst, A. T., Meyer, B.:
Beam-ACO Based on Stochastic Sampling for Makespan Optimization Concerning the TSP withTime Windows.
EvoCOP 2009, LNCS 5482:97-108 (2009)
López-Ibáñez, M., Blum, C.:
Beam-ACO for the travelling salesman problem with time windows.
Comput. Oper. Res., 37(9):1570-1583 (2010)
Karabulut, K., Tasgetiren, M. F.:
A variable iterated greedy algorithm for the traveling salesman problem with time windows.
Inform. Sci., 279:383-395 (2014)
Mladenović, M., Todosijević R., Urosević, D.:An efficient general variable neighborhood search for large travelling salesman problem with time
windows.
Yugoslav J. Oper. Res., 23(1):20-30 (2016)
Ohlmann, J. W., Thomas, B. W.:
A Compressed-Annealing Heuristic for the Traveling Salesman Problem with Time Windows.
INFORMS J. Comput., 19(1):80-90 (2007)
Pesant, G., Gendreau, M., Potvin, J.Y., Rousseau, J.M.:
An exact constraint logic programming algorithm for the travelling salesman problem with time
windows.
Transp. Sci., 32:12-29 (1998)
Potvin, J.Y., Bengio, S.:
The vehicle routing problem with time windows part II: genetic search.
INFORMS J. Comput., 8:165-172 (1996)
Silva, R. F. da, Urrutia, S.:
A General VNS heuristic for the traveling salesman problem with time windows.
Discrete Optim., 7(4):203-211 (2010)
Solomon, M. M.:
Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints.
Oper. Res., 35(2):254-265 (1987)

52

VRPB: Vehicle routing problem with backhauls
Brandão, J.:
A new tabu search algorithm for the vehicle routing problem with backhauls.
Eur. J. Oper. Res., 173(2):540-555 (2005)
Catay, B.:
Ant Colony Optimization and Its Application to the Vehicle Routing Problem with Pickups andDeliveries.
Studies in Computational Intelligence, 250:219-244 (2009)
Cuervo, D. P., Goos, P., Sörensen, K., Arráiz, E.:
An iterated local search algorithm for the vehicle routing problem with backhauls.
Eur. J. Oper. Res., 237(2):454-464 (2014)
Gajpal, Y., Abad, P. L.:
Multi-ant colony system (MACS) for a vehicle routing problem with backhauls.
Eur. J. Oper. Res., 196(1):102-117 (2009)
Gélinas, S., Desrochers, M., Desrosiers, J., Solomon, M. M.:
A new branching strategy for time constrained routing problems with application to backhauling.
Ann. Oper. Res., 61:91-109 (1995)
Ghaziri H., Osman, I. H.:
A neural network algorithm for the traveling salesman problem with backhauls.
Comput. Ind. Eng., 44(2):267-281 (2003)
Ghaziri H., Osman, I. H.:
Self-organizing feature maps for the vehicle routing problem with backhauls.
J. Sched. 9(2):97-114 (2006)
Goetschalckx M., Jacobs-Blecha C.
The vehicle routing problem with Backhauls.
Eur. J. Oper. Res., 42: 9-51 (1989)
Jacobs-Blecha, C. D., Goetscalckx, M.:
The Vehicle Routing Problem with Backhauls: Properties and Solution Algorithms.
Material Handling Research Center, Georgia Institute of Technology (1992)
Mingozzi, A., Giorgi, S., Baldacci, R.:
An Exact Method for the Vehicle Routing Problem with Backhauls.
Transp. Sci., 33(3):315-329 (1999)
Nagy, G., Salhi, S.:
Heuristic algorithms for single and multiple depot vehicle routing problems with pickups anddeliveries.
Eur. J. Oper. Res. 162(1):126-141 (2005)

53

Osman, I. H., Wassan, N. A.:
A reactive tabu search meta-heuristic for the vehicle routing problem with back-hauls.
J. Sched., 5(4):263-285 (2002)
Parragh, S.N., Doerner, K. F., Hartl, R. F.:
A survey on pickup and delivery problems. Part I: Transportation between customers and depot.
Journal für Betriebswirtschaft, 58(1):21-51 (2008)
Parragh, S.N., Doerner, K. F., Hartl, R. F.:
A survey on pickup and delivery problems. Part II: Transportation between pickup and delivery
locations.
Journal für Betriebswirtschaft, 58(2):81-117 (2008)
Pisinger, D., Ropke, S.:
A general heuristic for vehicle routing problems.
Comput. Oper. Res., 34(8):2403-2435 (2005)
Ropke, S., Pisinger, D.:
A unified heuristic for a large class of Vehicle Routing Problems with Backhauls.
Eur. J. Oper. Res., 171(3):750-775 (2006)
Toth, P., Vigo, D.:
An Exact Algorithm for the Vehicle Routing Problem with Backhauls.
Transp. Sci., 32(4):372-385 (1997)
Toth, P., Vigo, D.:
A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls.
Eur. J. Oper. Res., 113(3):528-543 (1999)
Wade, A., Salhi, S.:
An Ant System Algorithm for the Vehicle Routing Problem with Backhauls.
MIC’2001 - 4th Metaheuristics International Conference:199-203 (2001)
Wang, Z., Wang, Z.:
A novel two-phase heuristic method for vehicle routing problem with backhauls.
Comput. Math. Appl., 57(11-12):1923-1928 (2009)
Yalcin, G. D., Erginel, N.:
A Heuristic Based on Integer Programming for the Vehicle Routing Problem with Backhauls.
IEOM 2012:1350-1358 (2012)
Zachariadis, E. E., Kiranoudis, C. T.:
An Innovative Metaheuristic Solution Approach for the Vehicle Routing Problem with Backhauls.
Exp. Syst. Appl., 39(3):3174-3184 (2012)

54

VRPBTW: Vehicle routing problem with backhauls and time windows
Gélinas S., Desrochers, M., Desrosiers J., Solomon, M. M.:
A new branching strategy for time constrained routing problems with application to backhauling.
Ann. Oper. Res., 61:91-109 (1995)
Nalepa, J., Czech, Z. J.:
A Parallel Memetic Algorithm to Solve the Vehicle Routing Problem with Time Windows.
Studia Informatica, 33(1):91-106 (2012)
Reimann, M., Doerner, K., Hartl, R. F.:
Insertion Based Ants for Vehicle Routing Problems with Backhauls and Time Windows.
ANTS 2002, LNCS 2463:135-148 (2002)
Ropke, S., Pisinger, D.:
A unified heuristic for a large class of Vehicle Routing Problems with Backhauls.
Eur. J. Oper. Res., 171(3):750-775 (2006)
Ropke, S.:
Heuristic and exact algorithms for vehicle routing problems.
PhD thesis, DIKU, University of Copenhagen (2005)
Thangiah, S. R., Potvin, J.-Y., T. Sun, T.:
Heuristic Approaches to Vehicle Routing with Backhauls and Time Windows.
Comput. Oper. Res., 23(11):1043-1057 (1996)
Zhong, Y., Cole, M. H.:
A vehicle routing problem with backhauls and time windows: a guided local search solution.
Transp. Res., Part E 41:131-144 (2005)

55

VRPMPD: Vehicle routing problem with mixed pickup and delivery
Avci, M., Topaloglu, S.:
An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed
pickups and deliveries.
Comput. Ind. Eng., 83:15-29 (2015)
Catay, B.:
An ant colony algorithm for the mixed vehicle routing problem with backhauls.
3rd World Conference on Production and Operations Management, 9 pages (2008)
Crispim, J., Brandão, J.:
Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems withbackhauls.
J. Oper. Res. Soc., 56(11):1296-1302 (2005)
García-Nájera, A., Bullinaria, J., Gutiérrez-Andrade, M.;
An evolutionary approach for multi-objective vehicle routing problems with backhauls.
Comput. Ind. Eng., 81:90-108 (2015)
Nagy, G., Wassan, N. A., Salhi, S.:
The vehicle routing problem with restricted mixing of deliveries and pickups.
J. Sched., 16(2):199-213 (2013)
Salhi, S., Nagy, G.:A Cluster Insertion Heuristic for Single and Multiple Depot Vehicle Routing Problems with
Backhauling.
J. Oper. Res. Soc., 50(10):1034-1042 (1999)
Tütüncü, G. Y., Carreto, C. A. C., Baker, B. M.;
A visual interactive approach to classical and mixed vehicle routing problems with backhauls.
Omega, 37(1):138.154 (2009)

56

VRPMPDTW: Vehicle routing problem with mixed pickup and delivery and time windows
Gélinas S., Desrochers, M., Desrosiers J., Solomon, M. M.:
A new branching strategy for time constrained routing problems with application to backhauling.
Ann. Oper. Res., 61:91-109 (1995)
Nalepa, J., Czech, Z. J.:
A Parallel Memetic Algorithm to Solve the Vehicle Routing Problem with Time Windows.
Studia Informatica, 33(1):91-106 (2012)
Ropke, S., Pisinger, D.:
A unified heuristic for a large class of Vehicle Routing Problems with Backhauls.
Eur. J. Oper. Res., 171(3):750-775 (2006)
Ropke, S.:
Heuristic and exact algorithms for vehicle routing problems.
PhD thesis, DIKU, University of Copenhagen (2005)
Thangiah, S. R., Potvin, J.-Y., T. Sun, T.:
Heuristic Approaches to Vehicle Routing with Backhauls and Time Windows.
Comput. Oper. Res., 23(11):1043-1057 (1996)
Zhong, Y., Cole, M. H.:
A vehicle routing problem with backhauls and time windows: a guided local search solution.
Transp. Res., Part E 41:131-144 (2005)

57

VRPSPD: Vehicle routing problem with simultaneous pickup and delivery
Ai, T. J., Kachitvichyanukul, V.:
A particle swarm optimization for the vehicle routing problem with simultaneous pickup anddelivery.
Comput. Oper. Res., 36(5):1693-1702 (2009)
Avci, M., Topaloglu, S.:
An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed
pickups and deliveries.
Comput. Ind. Eng., 83:15-29 (2015)
B. Catay,
A new saving-based ant algorithm for the Vehicle Routing Problem with Simultaneous Pickup and
Delivery.
Expert Syst. Appl., 37(10):6809-6817 (2010)
Crispim, J., Brandão, J.:
Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems withbackhauls.
J. Oper. Res. Soc., 56(11):1296-1302 (2005)
Dethloff, J.:
Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery andpick-up.
OR Spektrum, 23(1):79-96 (2001)
Dethloff, J.:
Relation between Vehicle Routing Problems: An Insertion Heuristic for the Vehicle Routing
Problem with Simultaneous Delivery and Pick-Up Applied to the Vehicle Routing Problem with
Backhauls.
J. Oper. Res. Soc., 53(1):115-118 (2002)
Gajpal, Y., Abad, P.:
An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup.
Comput. Oper. Res., 36(12):3215-3223 (2009)
García-Nájera, A., Bullinaria, J., Gutiérrez-Andrade, M.;
An evolutionary approach for multi-objective vehicle routing problems with backhauls.
Comput. Ind. Eng., 81:90-108 (2015)

Jiang, Q., Wang, C., Mu, D., Zhou, L.:
A Hybrid Metaheuristic Algorithm for the VRPSPD Problem.
J. Comput. Inf. Syst., 11(13):4845-4856 (2015)
Jun, Y. Kim, B-I.,
New best solutions to VRPSPD benchmark problems by a perturbation based algorithm.

58

Exp. Syst. Appl., 29(5):5641-5648 (2012)
Kalayci, C. B., Kaya, C.:
An ant colony system empowered variable neighborhood search algorithm for the vehicle routing
problem with simultaneous pickup and delivery.
Exp. Syst. Appl., 66(30):163-175 (2016)
Li, J., Pardalos, M., Sun, H., Pei, J., Zhang, Y.:
Iterated local search embedded adaptive neighborhood selection approach for the multi-depot
vehicle routing problem with simultaneous deliveries and pickups.
Exp. Syst. Appl., 42(7):3551-3561 (2015)
Montané, F. A. T., Galvão, R. D.:
A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery
service.
Comput. Oper. Res., 33(3):595-619 (2006)
Phannikul, T., Sindhuchao, S.:
A Customized Tabu Search for the Vehicle Routing Problem with Simultaneous Pick-up and
Delivery.
Thammasat Int. J. Sci. Tech., 15(2):70-82 (2010)
Rieck, R., Zimmermann, J.:
Exact Solutions to the Symmetric and Asymmetric Vehicle Routing Problem with Simultaneous
Delivery and Pick-Up.
J. Bus. Res., 6(1):77-92 (2013)
Salhi, S., Nagy, G.:A Cluster Insertion Heuristic for Single and Multiple Depot Vehicle Routing Problems with
Backhauling.
J. Oper. Res. Soc., 50(10):1034-1042 (1999)
Shahdaei, A. M., Rahimi, A. M.:
Solving Vehicle Routing Problem with Simultaneous Pickup and Delivery with the Application of
Genetic Algorithm.
Indian Journal of Fundamental and Applied Life Sciences, 6:247-259 (2016)

59

VRPSPDTW: Vehicle routing problem with simultaneous pickup-delivery and time windows
Pisinger, D., Ropke, S.:
A general heuristic for vehicle routing problems.
Comput. Oper. Res., 34(8):2403-2435 (2005)
Wang, C., Mu, D., Zhao, F., Sutherland, J. W.:
A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–
delivery and time windows.
Comput. Ind. Eng., 83:111-122 (2015)60