×
Reiter, Peter; Gutjahr, Walter J.

Exact hybrid algorithms for solving a bi-objective vehicle routing problem. (English) Zbl 1245.90010

CEJOR, Cent. Eur. J. Oper. Res. 20, No. 1, 19-43 (2012).
Summary: The paper investigates a capacitated vehicle routing problem with two objectives: (1) minimization of total travel cost and (2) minimization of the length of the longest route. We present algorithmic variants for the exact determination of the Pareto-optimal solutions of this bi-objective problem. Our approach is based on the adaptive \(\varepsilon\)-constraint method. For solving the resulting single-objective subproblems, we apply a branch-and-cut technique, using (among others) a novel implementation of Held-Karp-type bounds. Incumbent solutions are generated by means of a single-objective genetic algorithm and, alternatively, by the multi-objective NSGA-II algorithm. Experimental results for a benchmark of 54 test instances from the TSPLIB are reported.

Cited in 7 Documents

MSC:

90B06 Transportation, logistics and supply chain management
90C27 Combinatorial optimization
90C29 Multi-objective and goal programming
90B10 Deterministic network models in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Keywords:

capacitated vehicle routing problem; distance constraints; multiobjective combinatorial optimization; branch-and-cut; TSPLIB

Software:

CVRPSP; VRP; CVRPSEP; weightedHypervolume
PDF BibTeX XML Cite
\textit{P. Reiter} and \textit{W. J. Gutjahr}, CEJOR, Cent. Eur. J. Oper. Res. 20, No. 1, 19--43 (2012; Zbl 1245.90010)
Full Text: DOI

References:

[1] Achuthan NR, Caccetta L, Hill SP (1996) A new subtour elimination constraint for the vehicle routing problem. Eur J Oper Res 91: 573–586 · Zbl 0924.90057
[2] Ascheuer N, Fischetti M, Grötschl M (2000) A polyhedral study of the asymmetric traveling salesman problem with time windows. Networks 36(2): 69–79 · Zbl 0972.90085
[3] Ascheuer N, Fischetti M, Grötschl M (2001) Solving the asymmetric travelling salesman problem with time windows by branch-and-cut. Math Program 90: 475–506 · Zbl 1039.90056
[4] Augerat P, Belenguer JM, Benavant E, Corberán A, Naddef D (1999) Seperating capacity inequalities in the CVRP using tabu search. Eur J Oper Res 106: 546–557 · Zbl 0991.90028
[5] Baldacci R, Hadjiconstantinou E, Mingozzi A (2004) An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Oper Res 52(5): 723–738 · Zbl 1165.90353
[6] Bektas T (2006) The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34(3): 209–219
[7] Bérubé J-F, Gendreau M, Potvin J-Y (2009) An exact {\(\epsilon\)}-constraint method for bi-objective combinatorial problems: application to the traveling salesman problem with profits. Eur J Oper Res 194: 39–50 · Zbl 1179.90274
[8] Chu F, Labadi N, Prins C (2006) A scatter search for the periodic capacitated arc routing problem. Eur J Oper Res 169(2): 586–605 · Zbl 1079.90028
[9] Deb K, Goel T (2001) Controlled elitist non-dominated sorting genetic algorithms for better convergence. In: First international conference on evolutionary multi-criterion optimization (EMO-2001)
[10] Deb K, Jain S (2002) Running performance metrics for evolutionary multi-objective optimization. KanGAL Report, 2002004
[11] Deb K, Pratap A, Meyarivan T (2000a) Constrained test problems for multi-objective evolutionary optimization. In: First international conference on evolutionary multi-criterion optimization, Springer, pp 284–298
[12] Deb K, Pratap A, Agarwal S, Meyarivan T (2000) A fast elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6: 182–197 · Zbl 05451853
[13] Fukasawa R, Longo H, Lysegaard J, Poggide Aragao M, Reis M, Uchoa E, Werneck R (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math Program 106(3): 491–511 · Zbl 1094.90050
[14] Haimes Y, Lasdon L, Wismer D (1971) On a bicriterion formulation of the problems of integrated system identification and system optimization. IEEE Trans Syst Man Cybern 1: 296–297 · Zbl 0224.93016
[15] Held M, Karp RM (1970) The traveling salesman problem and minimum spanning trees. Oper Res 18: 1135–1162 · Zbl 0226.90047
[16] Jozefowiez N, Semet F, Talbi EG (2002) Parallel and hybrid models for multi-objective optimization: application to the vehicle routing problem. In: Guervos J (eds) Parallel problem solving from nature–PPSN VII, LNCS. Springer, Granada
[17] Jozefowiez N, Semet F, Talbi EG (2006) Enhancements of NSGA-II and its application to the vehicle routing problem with route balancing. In: Talbi E (eds) Proceedings of the 7th international conference artificial evolution-EA 2005, number 3871 in LNCS, Springer, pp 131–142
[18] Jozefowiez N, Semet F, Talbi EG (2008) Multi-objective vehicle routing problems. Eur J Oper Res 189(2): 293–309 · Zbl 1148.90338
[19] Laporte G, Desrochers M, Nobert Y (1984) Two exact algorithms for the distance constrained vehicle routing problem. Networks 14: 161–172 · Zbl 0538.90093
[20] Laporte G, Mercure H, Nobert Y (1986) An exact algorithm for the asymmetrical capacitated vehicle routing problem. Networks 16 · Zbl 0643.90034
[21] Laumanns M, Thiele L, Zitzler E (2006) An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method. Eur J Oper Res 169(3) · Zbl 1079.90122
[22] Lysgaard J (2003) CVRPSEP: A package of seperations routines for the capacitated vehicle routing problem. http://www.hha.dk/\(\sim\)lys
[23] Lysgaard J, Letchford AN, Eglese RW (2003) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math Program 100: 2004
[24] Pasia JM, Doerner KF, Hartl RF, Reimann M (2007a) Solving a bi-objetive vehicle routing problem by pareto-ant colony optimization, vol 4638 of LNCS, pp 187–191. SLS 2007 · Zbl 1134.90313
[25] Pasia JM, Doerner KF, Hartl RF, Reimann M (2007b) A population-based local search for solving a bi-objective vehicle routing problem, vol 4446 of LNCS, pp 166–175. EvoCOP
[26] Prins C (2004) A simple and effective evolutionary algorithm for the vehicle routing problem. Comput Oper Res 31: 1985–2002 · Zbl 1100.90504
[27] Ralphs TK, Saltzman M, Wiecek M (2004) An improved algorithm for biobjective integer programming and its application to network routing problems. Ann Oper Res
[28] Toth P, Vigo D (eds) (2001) The vehicle routing problem, vol 9 of SIAM monographs on discrete mathematics and applications, SIAM · Zbl 0966.90009
[29] Tricoire F, Doerner KF, Hartl RF, Iori M (2009) Heuristic and exact algorithms for the multi-pile vehicle routing problem. Submitted to OR Spectrum · Zbl 1229.90039
[30] Valenzuela CL, Jones AJ (1997) Estimating the Held-Karp lower bound for the geometric TSP. Eur J Oper Res 102(1): 157–175 · Zbl 0948.90034
[31] Volgenant T, Jonker R (1982) A branch and bound algorithm for the symmetric traveling salesman problem based on 1-tree relaxation. Eur J Oper Res 9: 83–89 · Zbl 0471.90088
[32] Zitzler E, Thiele L (1998) Multiobjective optimization using evolutionary algorithms-a comparative case study. Lect Notes Comput Sci 292–304
[33] Zitzler E, Thiele L, Laumanns M, Fonseca CM, da Fonseca VG (2003) Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans Evol Comput 7(2): 117–132 · Zbl 05452216
[34] Zitzler E, Brockhoff D, Thiele L (2007) The hypervolume indicator revisited: on the design of pareto-compliant indicators via weighted integration. Lect Notes Comput Sci 4403: 862 · Zbl 05546545
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.