## Journal articles

My main research interests relate to combinatorial and continuous optimization, for applications related to vehicle routing, scheduling and timing, resource allocation, signal processing and machine learning. The associated journal publications are listed in the following.Many of these articles are made available as technical reports (CIRRELT or ArXiV) or post-print. To access these documents, simply click on the small PDF icon under the citation.

*(The list takes a few seconds to load)*

Excellent! Next, you can

**embed**this page using one of several options.To the site owner:

**Action required!** Mendeley is changing its
API. In order to keep using Mendeley with BibBase past April
14th, you need to:

- renew the authorization for BibBase on Mendeley, and
- update the BibBase URL in your page the same way you did when you initially set up this page.

2019
(16)

The electric two-echelon vehicle routing problem.
Breunig, U.; Baldacci, R.; Hartl, R.; and Vidal, T.

Paper doi bibtex

*Computers & Operations Research*, 103: 198–210. 2019.Paper doi bibtex

@article{Breunig2019, author = {Breunig, U. and Baldacci, R. and Hartl, R. and Vidal, T.}, doi = {10.1016/j.cor.2018.11.005}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Breunig et al/Breunig et al. - 2019 - The electric two-echelon vehicle routing problem(2).pdf:pdf}, journal = {Computers {\&} Operations Research}, mendeley-groups = {VRP-Var3-EVAL/Var3-EVAL-Electric/Vehicle Scheduling Paper}, pages = {198--210}, title = {{The electric two-echelon vehicle routing problem}}, url = {https://arxiv.org/pdf/1803.03628.pdf}, volume = {103}, year = {2019} }

On three soft rectangle packing problems with guillotine constraints.
Bui, Q.; Vidal, T.; and Hà, M.

Paper doi bibtex

*Journal of Global Optimization*, 74(1). 2019.Paper doi bibtex

@article{Bui2019, author = {Bui, Q.T. and Vidal, T. and H{\`{a}}, M.H.}, doi = {10.1007/s10898-019-00741-w}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Bui, Vidal, H{\`{a}}/Bui, Vidal, H{\`{a}} - 2019 - On three soft rectangle packing problems with guillotine constraints(3).pdf:pdf}, journal = {Journal of Global Optimization}, number = {1}, title = {{On three soft rectangle packing problems with guillotine constraints}}, url = {https://arxiv.org/pdf/1805.03631.pdf}, volume = {74}, year = {2019} }

Benchmark instances and branch-and-cut algorithm for the Hashiwokakero puzzle.
Coelho, L.; Laporte, G.; Lindbeck, A.; and Vidal, T.
Technical Report PUC-Rio, 2019.

Paper bibtex abstract

Paper bibtex abstract

@techreport{Coelho2019, abstract = {Hashiwokakero, or simply Hashi, is a Japanese single-player puzzle played on a rectangular grid with no standard size. Some cells of the grid contain a circle, called island, with a number inside it ranging from one to eight. The remaining positions of the grid are empty. The player must connect all of the islands by drawing a series of horizontal or vertical bridges between them, respecting a series of rules: the number of bridges incident to an island equals the number indicated in the circle, at most two bridges are incident to any side of an island, bridges cannot cross each other or pass through islands, and each island must eventually be reachable from any other island. In this paper, we present some complexity results and relationships between Hashi and well-known graph theory problems. We give a formulation of the problem by means of an integer linear mathematical programming model, and apply a branch-and-cut algorithm to solve the model in which connectivity constraints are dynamically generated. We also develop a puzzle generator. Our experiments on 1440 Hashi puzzles show that the algorithm can consistently solve hard puzzles with up to 400 islands.}, archivePrefix = {arXiv}, arxivId = {1905.00973}, author = {Coelho, L.C. and Laporte, G. and Lindbeck, A. and Vidal, T.}, eprint = {1905.00973}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Coelho et al/Coelho et al. - 2019 - Benchmark instances and branch-and-cut algorithm for the Hashiwokakero puzzle.pdf:pdf}, institution = {PUC-Rio}, title = {{Benchmark instances and branch-and-cut algorithm for the Hashiwokakero puzzle}}, url = {https://arxiv.org/pdf/1905.00973.pdf}, year = {2019} }

Hashiwokakero, or simply Hashi, is a Japanese single-player puzzle played on a rectangular grid with no standard size. Some cells of the grid contain a circle, called island, with a number inside it ranging from one to eight. The remaining positions of the grid are empty. The player must connect all of the islands by drawing a series of horizontal or vertical bridges between them, respecting a series of rules: the number of bridges incident to an island equals the number indicated in the circle, at most two bridges are incident to any side of an island, bridges cannot cross each other or pass through islands, and each island must eventually be reachable from any other island. In this paper, we present some complexity results and relationships between Hashi and well-known graph theory problems. We give a formulation of the problem by means of an integer linear mathematical programming model, and apply a branch-and-cut algorithm to solve the model in which connectivity constraints are dynamically generated. We also develop a puzzle generator. Our experiments on 1440 Hashi puzzles show that the algorithm can consistently solve hard puzzles with up to 400 islands.

To team up or not – Single versus team driving in European road freight transport.
Goel, A.; Vidal, T.; and Kok, A.
Technical Report PUC–Rio, Rio de Janeiro, Brasil, 2019.

Paper bibtex

Paper bibtex

@techreport{Goel2019, address = {Rio de Janeiro, Brasil}, author = {Goel, A. and Vidal, T. and Kok, A.L.}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Goel, Vidal, Kok/Goel, Vidal, Kok - 2019 - To team up or not – Single versus team driving in European road freight transport(2).pdf:pdf}, institution = {PUC--Rio}, title = {{To team up or not – Single versus team driving in European road freight transport}}, url = {https://w1.cirrelt.ca/{~}vidalt/papers/Team-vs-Single.pdf}, year = {2019} }

HG-means: A scalable hybrid metaheuristic for minimum sum-of-squares clustering.
Gribel, D.; and Vidal, T.

Paper doi bibtex abstract

*Pattern Recognition*, 88: 569–583. 2019.Paper doi bibtex abstract

@article{Gribel2019, abstract = {Minimum sum-of-squares clustering (MSSC) is a widely used clustering model, of which the popular K-means algorithm constitutes a local minimizer. It is well known that the solutions of K-means can be arbitrarily distant from the true MSSC global optimum, and dozens of alternative heuristics have been proposed for this problem. However, no other algorithm has been commonly adopted in the literature. This may be related to differences of computational effort, or to the assumption that a better solution of the MSSC has only a minor impact on classification or generalization capabilities. In this article, we dispute this belief. We introduce an efficient population-based metaheuristic that uses K-means as a local search in combination with problem-tailored crossover, mutation, and diversification operators. This algorithm can be interpreted as a multi-start K-means, in which the initial center positions are carefully sampled based on the search history. The approach is scalable and accurate, outperforming all recent state-of-the-art algorithms for MSSC in terms of solution quality, measured by the depth of local minima. This enhanced accuracy leads to classification results which are significantly closer to the ground truth than those of other algorithms, for overlapping Gaussian-mixture datasets with a large number of features and clusters. Therefore, improved global optimization methods appear to be essential to better exploit the MSSC model in high dimension.}, author = {Gribel, D. and Vidal, T.}, doi = {10.1016/j.patcog.2018.12.022}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Gribel, Vidal/Gribel, Vidal - 2019 - HG-means A scalable hybrid metaheuristic for minimum sum-of-squares clustering(3).pdf:pdf}, journal = {Pattern Recognition}, pages = {569--583}, title = {{HG-means: A scalable hybrid metaheuristic for minimum sum-of-squares clustering}}, url = {https://arxiv.org/pdf/1804.09813.pdf}, volume = {88}, year = {2019} }

Minimum sum-of-squares clustering (MSSC) is a widely used clustering model, of which the popular K-means algorithm constitutes a local minimizer. It is well known that the solutions of K-means can be arbitrarily distant from the true MSSC global optimum, and dozens of alternative heuristics have been proposed for this problem. However, no other algorithm has been commonly adopted in the literature. This may be related to differences of computational effort, or to the assumption that a better solution of the MSSC has only a minor impact on classification or generalization capabilities. In this article, we dispute this belief. We introduce an efficient population-based metaheuristic that uses K-means as a local search in combination with problem-tailored crossover, mutation, and diversification operators. This algorithm can be interpreted as a multi-start K-means, in which the initial center positions are carefully sampled based on the search history. The approach is scalable and accurate, outperforming all recent state-of-the-art algorithms for MSSC in terms of solution quality, measured by the depth of local minima. This enhanced accuracy leads to classification results which are significantly closer to the ground truth than those of other algorithms, for overlapping Gaussian-mixture datasets with a large number of features and clusters. Therefore, improved global optimization methods appear to be essential to better exploit the MSSC model in high dimension.

Two-dimensional phase unwrapping via balanced spanning forests.
Herszterg, I.; Poggi, M.; and Vidal, T.

Paper doi bibtex abstract

*INFORMS Journal on Computing, Articles in Advance*. 2019.Paper doi bibtex abstract

@article{Herszterg2019, abstract = {Phase unwrapping is the process of recovering a continuous phase signal from an original signal wrapped in the (−$\pi$,$\pi$] interval. It is a critical step of coherent signal processing, with applications such as synthetic aperture radar, acoustic imaging, magnetic resonance, X-ray crystallography, and seismic processing. In the field of computational optics, this problem is classically treated as a norm-minimization problem, in which one seeks to minimize the differences between the gradients of the original wrapped signal and those of the continuous unwrapped signal. When the L 0 –norm is considered, the number of differences should be minimized, leading to a difficult combinatorial optimization problem. We propose an approximate model for the L 0 –norm phase unwrapping problem in 2D, in which the singularities of the wrapped phase image are associated with a graph where the vertices have −1 or +1 polarities. The objective is to find a minimum-cost balanced spanning forest where the sum of the polarities is equal to zero in each tree. We introduce a set of primal and dual heuristics, a branch-and-cut algorithm, and a hybrid metaheuristic to efficiently find exact or heuristic solutions. These approaches move us one step closer to optimal solutions for 2D L 0 –norm phase unwrapping; such solutions were previously viewed, in the signal processing literature, as highly desirable but intractable.}, author = {Herszterg, I. and Poggi, M. and Vidal, T.}, doi = {10.1287/ijoc.2018.0832}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Herszterg, Poggi, Vidal/Herszterg, Poggi, Vidal - 2019 - Two-dimensional phase unwrapping via balanced spanning forests.pdf:pdf}, institution = {PUC-Rio}, journal = {INFORMS Journal on Computing, Articles in Advance}, title = {{Two-dimensional phase unwrapping via balanced spanning forests}}, url = {https://arxiv.org/pdf/1812.08277.pdf}, year = {2019} }

Phase unwrapping is the process of recovering a continuous phase signal from an original signal wrapped in the (−$\pi$,$\pi$] interval. It is a critical step of coherent signal processing, with applications such as synthetic aperture radar, acoustic imaging, magnetic resonance, X-ray crystallography, and seismic processing. In the field of computational optics, this problem is classically treated as a norm-minimization problem, in which one seeks to minimize the differences between the gradients of the original wrapped signal and those of the continuous unwrapped signal. When the L 0 –norm is considered, the number of differences should be minimized, leading to a difficult combinatorial optimization problem. We propose an approximate model for the L 0 –norm phase unwrapping problem in 2D, in which the singularities of the wrapped phase image are associated with a graph where the vertices have −1 or +1 polarities. The objective is to find a minimum-cost balanced spanning forest where the sum of the polarities is equal to zero in each tree. We introduce a set of primal and dual heuristics, a branch-and-cut algorithm, and a hybrid metaheuristic to efficiently find exact or heuristic solutions. These approaches move us one step closer to optimal solutions for 2D L 0 –norm phase unwrapping; such solutions were previously viewed, in the signal processing literature, as highly desirable but intractable.

Restriction policies for sustainable city logistics.
Hiermann, G.; Hartl, R.; Puchinger, J.; Schiffer, M.; and Vidal, T.
Technical Report University of Vienna, Austria, 2019.

bibtex

bibtex

@techreport{Hiermann2019a, author = {Hiermann, G. and Hartl, R.F. and Puchinger, J. and Schiffer, M. and Vidal, T.}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Hiermann et al/Hiermann et al. - 2019 - Restriction policies for sustainable city logistics.pdf:pdf}, institution = {University of Vienna, Austria}, title = {{Restriction policies for sustainable city logistics}}, year = {2019} }

Routing a mix of conventional, plug-in hybrid, and electric vehicles.
Hiermann, G.; Hartl, R.; Puchinger, J.; and Vidal, T.

Paper doi bibtex

*European Journal of Operational Research*, 272(1): 235–248. 2019.Paper doi bibtex

@article{Hiermann2019, author = {Hiermann, G. and Hartl, R.F. and Puchinger, J. and Vidal, T.}, doi = {10.1016/j.ejor.2018.06.025}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Hiermann et al/Hiermann et al. - 2019 - Routing a mix of conventional, plug-in hybrid, and electric vehicles.pdf:pdf}, journal = {European Journal of Operational Research}, mendeley-groups = {VRP-Objectives/6. EXTERNALITIES,VRP-Objectives/6. EXTERNALITIES/Pollution/Electric,VRP-Var3-EVAL/Var3-EVAL-Electric,VRP-Var3-EVAL/Var3-EVAL-Electric/Vehicle Scheduling Paper}, number = {1}, pages = {235--248}, title = {{Routing a mix of conventional, plug-in hybrid, and electric vehicles}}, url = {https://hal.archives-ouvertes.fr/hal-01668228/document}, volume = {272}, year = {2019} }

Mathematical models and search algorithms for the capacitated p-center problem.
Kramer, R.; Iori, M.; and Vidal, T.

Paper bibtex abstract

*INFORMS Journal on Computing, Forthcoming*. 2019.Paper bibtex abstract

@article{Kramer2019a, abstract = {The capacitated p-center problem requires to select p facilities from a set of candidates to service a number of customers, subject to facility capacity constraints, with the aim of minimizing the maximum distance between a customer and its associated facility. The problem is well known in the field of facility location, because of the many applications that it can model. In this paper, we solve it by means of search algorithms that iteratively seek the optimal distance by solving tailored subproblems. We present different mathematical formulations for the subproblems and improve them by means of several valid inequalities, including an effective one based on a 0-1 disjunction and the solution of subset sum problems. We also develop an alternative search strategy that finds a balance between the traditional sequential search and binary search. This strategy limits the number of feasible subproblems to be solved and, at the same time, avoids large overestimates of the solution value, which are detrimental for the search. We evaluate the proposed techniques by means of extensive computational experiments on benchmark instances from the literature and new larger test sets. All instances from the literature with up to 402 vertices and integer distances are solved to proven optimality, including 13 open cases, and feasible solutions are found in 10 minutes for instances with up to 3038 vertices.}, author = {Kramer, R. and Iori, M. and Vidal, T.}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Kramer, Iori, Vidal/Kramer, Iori, Vidal - 2019 - Mathematical models and search algorithms for the capacitated p-center problem.pdf:pdf}, journal = {INFORMS Journal on Computing, Forthcoming}, title = {{Mathematical models and search algorithms for the capacitated p-center problem}}, url = {https://arxiv.org/pdf/1803.04865.pdf}, year = {2019} }

The capacitated p-center problem requires to select p facilities from a set of candidates to service a number of customers, subject to facility capacity constraints, with the aim of minimizing the maximum distance between a customer and its associated facility. The problem is well known in the field of facility location, because of the many applications that it can model. In this paper, we solve it by means of search algorithms that iteratively seek the optimal distance by solving tailored subproblems. We present different mathematical formulations for the subproblems and improve them by means of several valid inequalities, including an effective one based on a 0-1 disjunction and the solution of subset sum problems. We also develop an alternative search strategy that finds a balance between the traditional sequential search and binary search. This strategy limits the number of feasible subproblems to be solved and, at the same time, avoids large overestimates of the solution value, which are detrimental for the search. We evaluate the proposed techniques by means of extensive computational experiments on benchmark instances from the literature and new larger test sets. All instances from the literature with up to 402 vertices and integer distances are solved to proven optimality, including 13 open cases, and feasible solutions are found in 10 minutes for instances with up to 3038 vertices.

Leveraging single-objective heuristics to solve multi-objective problems: Heuristic box splitting and its application to vehicle routing.
Matl, P.; Hartl, R.; and Vidal, T.

doi bibtex

*Networks*, 73(4): 382–400. 2019.doi bibtex

@article{Matl2019, author = {Matl, P. and Hartl, R.F. and Vidal, T.}, doi = {10.1002/net.21876}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Matl, Hartl, Vidal/Matl, Hartl, Vidal - 2019 - Leveraging single-objective heuristics to solve multi-objective problems Heuristic box splitting and its (3).pdf:pdf}, journal = {Networks}, number = {4}, pages = {382--400}, title = {{Leveraging single-objective heuristics to solve multi-objective problems: Heuristic box splitting and its application to vehicle routing}}, volume = {73}, year = {2019} }

Workload equity in vehicle routing: The impact of alternative workload resources.
Matl, P.; Hartl, R.; and Vidal, T.

Paper doi bibtex

*Computers & Operations Research*, 110: 116–129. 2019.Paper doi bibtex

@article{Matl2018a, author = {Matl, P. and Hartl, R.F. and Vidal, T.}, doi = {10.1016/j.cor.2019.05.016}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Matl, Hartl, Vidal/Matl, Hartl, Vidal - 2019 - Workload equity in vehicle routing The impact of alternative workload resources(2).pdf:pdf}, journal = {Computers {\&} Operations Research}, mendeley-groups = {VRP-Objectives/1. EQUITY}, pages = {116--129}, title = {{Workload equity in vehicle routing: The impact of alternative workload resources}}, url = {https://arxiv.org/pdf/1803.01795.pdf}, volume = {110}, year = {2019} }

A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet.
Penna, P.; Subramanian, A.; Ochi, L.; Vidal, T.; and Prins, C.

Paper doi bibtex

*Annals of Operations Research*, 273(1-2): 5–74. 2019.Paper doi bibtex

@article{Penna2019, author = {Penna, P.H.V. and Subramanian, A. and Ochi, L.S. and Vidal, T. and Prins, C.}, doi = {10.1007/s10479-017-2642-9}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Penna et al/Penna et al. - 2019 - A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet.pdf:pdf}, journal = {Annals of Operations Research}, keywords = {Heterogeneous fleet,Iterated local search,Matheuristics,Rich vehicle routing,Set partitioning}, number = {1-2}, pages = {5--74}, title = {{A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet}}, url = {https://arxiv.org/pdf/1803.01930.pdf}, volume = {273}, year = {2019} }

The vehicle routing problem with arrival time diversification on a multigraph.
Soriano, A.; Vidal, T.; Gansterer, M.; and Doerner, K.
Technical Report University of Vienna, Austria, 2019.

bibtex

bibtex

@techreport{Soriano2019, author = {Soriano, A. and Vidal, T. and Gansterer, M. and Doerner, K.}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Soriano et al/Soriano et al. - 2019 - The vehicle routing problem with arrival time diversification on a multigraph.pdf:pdf}, institution = {University of Vienna, Austria}, title = {{The vehicle routing problem with arrival time diversification on a multigraph}}, year = {2019} }

Heuristics for vehicle routing problems: Sequence or set optimization?.
Toffolo, T.; Vidal, T.; and Wauters, T.

Paper doi bibtex abstract

*Computers & Operations Research*, 105: 118–131. 2019.Paper doi bibtex abstract

@article{Toffolo2019, abstract = {We investigate a structural decomposition for the capacitated vehicle routing problem (CVRP) based on vehicle-to-customer “assignment” and visits “sequencing” decision variables. We show that an heuristic search focused on assignment decisions with a systematic optimal choice of sequences (using Concorde TSP solver) during each move evaluation is promising but requires a prohibitive computational effort. We therefore introduce an intermediate search space, based on the dynamic programming procedure of Balas {\&} Simonetti, which finds a good compromise between intensification and computational efficiency. A variety of speed-up techniques are proposed for a fast exploration: neighborhood reductions, dynamic move filters, memory structures, and concatenation techniques. Finally, a tunneling strategy is designed to reshape the search space as the algorithm progresses. The combination of these techniques within a classical local search, as well as in the unified hybrid genetic search (UHGS) leads to significant improvements of solution accuracy. New best solutions are found for surprisingly small instances with as few as 256 customers. These solutions had not been attained up to now with classic neighborhoods. Overall, this research permits to better evaluate the respective impact of sequence and assignment optimization, proposes new ways of combining the optimization of these two decision sets, and opens promising research perspectices for the CVRP and its variants}, author = {Toffolo, T.A.M. and Vidal, T. and Wauters, T.}, doi = {10.1016/j.cor.2018.12.023}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Toffolo, Vidal, Wauters/Toffolo, Vidal, Wauters - 2019 - Heuristics for vehicle routing problems Sequence or set optimization(2).pdf:pdf}, journal = {Computers {\&} Operations Research}, pages = {118--131}, title = {{Heuristics for vehicle routing problems: Sequence or set optimization?}}, url = {https://arxiv.org/pdf/1803.06062.pdf}, volume = {105}, year = {2019} }

We investigate a structural decomposition for the capacitated vehicle routing problem (CVRP) based on vehicle-to-customer “assignment” and visits “sequencing” decision variables. We show that an heuristic search focused on assignment decisions with a systematic optimal choice of sequences (using Concorde TSP solver) during each move evaluation is promising but requires a prohibitive computational effort. We therefore introduce an intermediate search space, based on the dynamic programming procedure of Balas & Simonetti, which finds a good compromise between intensification and computational efficiency. A variety of speed-up techniques are proposed for a fast exploration: neighborhood reductions, dynamic move filters, memory structures, and concatenation techniques. Finally, a tunneling strategy is designed to reshape the search space as the algorithm progresses. The combination of these techniques within a classical local search, as well as in the unified hybrid genetic search (UHGS) leads to significant improvements of solution accuracy. New best solutions are found for surprisingly small instances with as few as 256 customers. These solutions had not been attained up to now with classic neighborhoods. Overall, this research permits to better evaluate the respective impact of sequence and assignment optimization, proposes new ways of combining the optimization of these two decision sets, and opens promising research perspectices for the CVRP and its variants

Separable convex optimization with nested lower and upper constraints.
Vidal, T.; Gribel, D.; and Jaillet, P.

Paper doi bibtex abstract

*INFORMS Journal on Optimization*, 1(1): 71–90. 2019.Paper doi bibtex abstract

@article{Vidal2019a, abstract = {We study a convex resource allocation problem in which lower and upper bounds are imposed on partial sums of allocations. This model is linked to a large range of applications, including production planning, speed optimization, stratified sampling, support vector machines, portfolio management, and telecommunications. We propose an efficient gradient-free divide-and-conquer algorithm, which uses monotonicity arguments to generate valid bounds from the recursive calls, and eliminate linking constraints based on the information from sub-problems. This algorithm does not need strict convexity or differentiability. It produces an {\$}\backslashepsilon{\$}-approximate solution for the continuous version of the problem in {\$}\backslashmathcal{\{}O{\}}(n \backslashlog m \backslashlog \backslashfrac{\{}n B{\}}{\{}\backslashepsilon{\}}){\$} operations and an integer solution in {\$}\backslashmathcal{\{}O{\}}(n \backslashlog m \backslashlog B){\$}, where {\$}n{\$} is the number of decision variables, {\$}m{\$} is the number of constraints, and {\$}B{\$} is the resource bound. A complexity of {\$}\backslashmathcal{\{}O{\}}(n \backslashlog m){\$} is also achieved for the linear and quadratic cases. These are the best complexities known to date for this important problem class. Our experimental analyses confirm the practical performance of the method, which produces optimal solutions for problems with up to 1,000,000 variables in a few seconds. Promising applications to the support vector ordinal regression problem are also investigated.}, author = {Vidal, T. and Gribel, D. and Jaillet, P.}, doi = {10.1287/ijoo.2018.0004}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal, Gribel, Jaillet/Vidal, Gribel, Jaillet - 2019 - Separable convex optimization with nested lower and upper constraints(2).pdf:pdf}, journal = {INFORMS Journal on Optimization}, number = {1}, pages = {71--90}, title = {{Separable convex optimization with nested lower and upper constraints}}, url = {http://arxiv.org/pdf/1703.01484.pdf}, volume = {1}, year = {2019} }

We study a convex resource allocation problem in which lower and upper bounds are imposed on partial sums of allocations. This model is linked to a large range of applications, including production planning, speed optimization, stratified sampling, support vector machines, portfolio management, and telecommunications. We propose an efficient gradient-free divide-and-conquer algorithm, which uses monotonicity arguments to generate valid bounds from the recursive calls, and eliminate linking constraints based on the information from sub-problems. This algorithm does not need strict convexity or differentiability. It produces an \$}\backslashepsilon{\$-approximate solution for the continuous version of the problem in \$}\backslashmathcal{\{}O{\}}(n \backslashlog m \backslashlog \backslashfrac{\{}n B{\}}{\{}\backslashepsilon{\}}){\$ operations and an integer solution in \$}\backslashmathcal{\{}O{\}}(n \backslashlog m \backslashlog B){\$, where \$}n{\$ is the number of decision variables, \$}m{\$ is the number of constraints, and \$}B{\$ is the resource bound. A complexity of \$}\backslashmathcal{\{}O{\}}(n \backslashlog m){\$ is also achieved for the linear and quadratic cases. These are the best complexities known to date for this important problem class. Our experimental analyses confirm the practical performance of the method, which produces optimal solutions for problems with up to 1,000,000 variables in a few seconds. Promising applications to the support vector ordinal regression problem are also investigated.

A concise guide to existing and emerging vehicle routing problem variants.
Vidal, T.; Laporte, G.; and Matl, P.
Technical Report Pontifical Catholic University of Rio de Janeiro, 2019.

Paper bibtex abstract

Paper bibtex abstract

@techreport{Vidal2019, abstract = {Vehicle routing problems have been the focus of extensive research over the past sixty years, driven by their economic importance and their theoretical interest. The diversity of applications has motivated the study of a myriad of problem variants with different attributes. In this article, we provide a brief survey of existing and emerging problem variants. Models are typically refined along three lines: considering more relevant objectives and performance metrics, integrating vehicle routing evaluations with other tactical decisions, and capturing fine-grained yet essential aspects of modern supply chains. We organize the main problem attributes within this structured framework. We discuss recent research directions and pinpoint current shortcomings, recent successes, and emerging challenges.}, archivePrefix = {arXiv}, arxivId = {1906.06750}, author = {Vidal, T. and Laporte, G. and Matl, P.}, eprint = {1906.06750}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal, Laporte, Matl/Vidal, Laporte, Matl - 2019 - A concise guide to existing and emerging vehicle routing problem variants.pdf:pdf}, institution = {Pontifical Catholic University of Rio de Janeiro}, title = {{A concise guide to existing and emerging vehicle routing problem variants}}, url = {http://arxiv.org/abs/1906.06750}, year = {2019} }

Vehicle routing problems have been the focus of extensive research over the past sixty years, driven by their economic importance and their theoretical interest. The diversity of applications has motivated the study of a myriad of problem variants with different attributes. In this article, we provide a brief survey of existing and emerging problem variants. Models are typically refined along three lines: considering more relevant objectives and performance metrics, integrating vehicle routing evaluations with other tactical decisions, and capturing fine-grained yet essential aspects of modern supply chains. We organize the main problem attributes within this structured framework. We discuss recent research directions and pinpoint current shortcomings, recent successes, and emerging challenges.

2018
(10)

An efficient matheuristic for the minimum-weight dominating set problem.
Albuquerque, M.; and Vidal, T.

Paper doi bibtex abstract

*Applied Soft Computing*, 72: 527–538. 2018.Paper doi bibtex abstract

@article{Albuquerque2018, abstract = {A minimum dominating set in a graph is a minimum set of vertices such that every vertex of the graph belongs either to it, or is adjacent to one vertex of this set. This mathematical object is of high relevance in a number of applications related to wireless networks design, coding theory, and data mining, among many others. When vertices weights are given, minimizing the total weight of the dominating set gives rise to a problem variant known as the minimum weight dominating set problem. To solve this problem, we introduce a hybrid matheuristic combining a tabu search with an integer programming solver, used to solve subproblems in which only a minority of decision variables, selected relatively to the search history, are left free while the others are fixed. Moreover, we introduce an adaptive penalty to promote the exploration of intermediate infeasible solutions in the search, enhance the algorithm with perturbations and node elimination procedures, and exploit richer neighborhood classes. Extensive experimental analyses on a variety of instance classes demonstrate the good performance of the algorithm, and the contribution of each component in the success of the search is analyzed.}, author = {Albuquerque, M. and Vidal, T.}, doi = {https://doi.org/10.1016/j.asoc.2018.06.052}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Albuquerque, Vidal/Albuquerque, Vidal - 2018 - An efficient matheuristic for the minimum-weight dominating set problem.pdf:pdf}, journal = {Applied Soft Computing}, keywords = {hybrid metaheuristics,integer,large neighborhood search,matheuristics,minimum weight dominating set,programming}, pages = {527--538}, title = {{An efficient matheuristic for the minimum-weight dominating set problem}}, url = {https://arxiv.org/pdf/1808.09809.pdf}, volume = {72}, year = {2018} }

A minimum dominating set in a graph is a minimum set of vertices such that every vertex of the graph belongs either to it, or is adjacent to one vertex of this set. This mathematical object is of high relevance in a number of applications related to wireless networks design, coding theory, and data mining, among many others. When vertices weights are given, minimizing the total weight of the dominating set gives rise to a problem variant known as the minimum weight dominating set problem. To solve this problem, we introduce a hybrid matheuristic combining a tabu search with an integer programming solver, used to solve subproblems in which only a minority of decision variables, selected relatively to the search history, are left free while the others are fixed. Moreover, we introduce an adaptive penalty to promote the exploration of intermediate infeasible solutions in the search, enhance the algorithm with perturbations and node elimination procedures, and exploit richer neighborhood classes. Extensive experimental analyses on a variety of instance classes demonstrate the good performance of the algorithm, and the contribution of each component in the success of the search is analyzed.

Bi-objective Offshore Supply Vessel Planning with Costs and Persistence Objectives.
Borthen, T.; Loennechen, H.; Fagerholt, K.; Wang, X.; and Vidal, T.
Technical Report Norwegian University of Science and Technology, 2018.

bibtex

bibtex

@techreport{Borthen2018a, author = {Borthen, T. and Loennechen, H. and Fagerholt, K. and Wang, X. and Vidal, T.}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Borthen et al/Borthen et al. - 2018 - Bi-objective Offshore Supply Vessel Planning with Costs and Persistence Objectives.pdf:pdf}, institution = {Norwegian University of Science and Technology}, title = {{Bi-objective Offshore Supply Vessel Planning with Costs and Persistence Objectives}}, year = {2018} }

A genetic search-based heuristic for a fleet size and periodic routing problem with application to offshore supply planning.
Borthen, T.; Loennechen, H.; Wang, X.; Fagerholt, K.; and Vidal, T.

Paper doi bibtex abstract

*EURO Journal on Transportation and Logistics*, 7(2): 121–150. 2018.Paper doi bibtex abstract

@article{Borthen2018, abstract = {This paper introduces a genetic search-based heuristic to solve an offshore supply vessel planning problem (SVPP) faced by the Norwegian oil and gas company Statoil. The aim is to help the company in determining the optimal size of supply vessels to charter in and their corresponding voyages and schedules. We take inspiration from the hybrid genetic search with adaptive diversity control (HGSADC) algorithm of Vidal et al. (Oper Res 60(3):611–624, 2012), which successfully addresses a large class of vehicle routing problems, including the multi-period VRP (PVRP), and adapt it to account for some special features that are recurrent in maritime transportation but scarcely found in classical PVRPs, in particular, the possibility of having voyages spanning over multiple time periods in the planning horizon. Our computational experiments show that the proposed heuristic is scalable and stable, being able to solve industrial SVPPs of realistic size while significantly outperforming the existing approaches.}, author = {Borthen, T. and Loennechen, H. and Wang, X. and Fagerholt, K. and Vidal, T.}, doi = {10.1007/s13676-017-0111-x}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Borthen et al/Borthen et al. - 2018 - A genetic search-based heuristic for a fleet size and periodic routing problem with application to offshore supp.pdf:pdf}, journal = {EURO Journal on Transportation and Logistics}, number = {2}, pages = {121--150}, title = {{A genetic search-based heuristic for a fleet size and periodic routing problem with application to offshore supply planning}}, url = {http://link.springer.com/10.1007/s13676-017-0111-x}, volume = {7}, year = {2018} }

This paper introduces a genetic search-based heuristic to solve an offshore supply vessel planning problem (SVPP) faced by the Norwegian oil and gas company Statoil. The aim is to help the company in determining the optimal size of supply vessels to charter in and their corresponding voyages and schedules. We take inspiration from the hybrid genetic search with adaptive diversity control (HGSADC) algorithm of Vidal et al. (Oper Res 60(3):611–624, 2012), which successfully addresses a large class of vehicle routing problems, including the multi-period VRP (PVRP), and adapt it to account for some special features that are recurrent in maritime transportation but scarcely found in classical PVRPs, in particular, the possibility of having voyages spanning over multiple time periods in the planning horizon. Our computational experiments show that the proposed heuristic is scalable and stable, being able to solve industrial SVPPs of realistic size while significantly outperforming the existing approaches.

The vehicle routing problem with service level constraints.
Bulhões, T.; Hà, M.; Martinelli, R.; and Vidal, T.

Paper bibtex abstract

*European Journal of Operational Research*, 265(2): 544–558. 2018.Paper bibtex abstract

@article{Bulhoes2018, abstract = {We consider a vehicle routing problem which seeks to minimize cost subject to service level constraints on several groups of deliveries. This problem captures some essential challenges faced by a logistics provider which operates transportation services for a limited number of partners and should respect contractual obligations on service levels. The problem also generalizes several important classes of vehicle routing problems with profits. To solve it, we propose a compact mathematical formulation, a branch-and-price algorithm, and a hybrid genetic algorithm with population management, which relies on problem-tailored solution representation, crossover and local search operators, as well as an adaptive penalization mechanism establishing a good balance between service levels and costs. Our computational experiments show that the proposed heuristic returns very high-quality solutions for this difficult problem, matches all optimal solutions found for small and medium-scale benchmark instances, and improves upon existing algorithms for two important special cases: the vehicle routing problem with private fleet and common carrier, and the capacitated profitable tour problem. The branch-and-price algorithm also produces new optimal solutions for all three problems.}, archivePrefix = {arXiv}, arxivId = {1706.03097}, author = {Bulh{\~{o}}es, T. and H{\`{a}}, M.H. and Martinelli, R. and Vidal, T.}, eprint = {1706.03097}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Bulh{\~{o}}es et al/Bulh{\~{o}}es et al. - 2018 - The vehicle routing problem with service level constraints.pdf:pdf}, journal = {European Journal of Operational Research}, keywords = {branch-and-cut,genetic,service level constraints,vehicle routing problem}, mendeley-groups = {Metaheuristics/Decompositions,VRP-Var1-ASSIGN/Var1-ASSIGN-Service-Levels}, number = {2}, pages = {544--558}, title = {{The vehicle routing problem with service level constraints}}, url = {https://arxiv.org/pdf/1706.03097.pdf}, volume = {265}, year = {2018} }

We consider a vehicle routing problem which seeks to minimize cost subject to service level constraints on several groups of deliveries. This problem captures some essential challenges faced by a logistics provider which operates transportation services for a limited number of partners and should respect contractual obligations on service levels. The problem also generalizes several important classes of vehicle routing problems with profits. To solve it, we propose a compact mathematical formulation, a branch-and-price algorithm, and a hybrid genetic algorithm with population management, which relies on problem-tailored solution representation, crossover and local search operators, as well as an adaptive penalization mechanism establishing a good balance between service levels and costs. Our computational experiments show that the proposed heuristic returns very high-quality solutions for this difficult problem, matches all optimal solutions found for small and medium-scale benchmark instances, and improves upon existing algorithms for two important special cases: the vehicle routing problem with private fleet and common carrier, and the capacitated profitable tour problem. The branch-and-price algorithm also produces new optimal solutions for all three problems.

A study on exponential-size neighborhoods for the bin packing problem with conflicts.
Capua, R.; Frota, Y.; Ochi, L.; and Vidal, T.

Paper doi bibtex

*Journal of Heuristics*, 24(4): 667–695. 2018.Paper doi bibtex

@article{Capua2018, author = {Capua, R. and Frota, Y. and Ochi, L.S. and Vidal, T.}, doi = {10.1007/s10732-018-9372-2}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Capua et al/Capua et al. - 2018 - A study on exponential-size neighborhoods for the bin packing problem with conflicts(2).pdf:pdf}, journal = {Journal of Heuristics}, number = {4}, pages = {667--695}, title = {{A study on exponential-size neighborhoods for the bin packing problem with conflicts}}, url = {http://arxiv.org/pdf/1705.08495.pdf}, volume = {24}, year = {2018} }

The minimum distance superset problem: Formulations and algorithms.
Fontoura, L.; Martinelli, R.; Poggi, M.; and Vidal, T.

Paper doi bibtex abstract

*Journal of Global Optimization*, 72(1): 27–53. 2018.Paper doi bibtex abstract

@article{Fontoura2017, abstract = {The partial digest problem consists in retrieving the positions of a set of points on the real line from their unlabeled pairwise distances. This problem is critical for DNA sequencing, as well as for phase retrieval in X-ray crystallography. When some of the distances are missing, this problem generalizes into a “minimum distance superset problem”, which aims to find a set of points of minimum cardinality such that the multiset of their pairwise distances is a superset of the input. We introduce a quadratic integer programming formulation for the minimum distance superset problem with a pseudo-polynomial number of variables, as well as a polynomial-size integer programming formulation. We investigate three types of solution approaches based on an available integer programming solver: (1) solving a linearization of the pseudo-polynomial-sized formulation, (2) solving the complete polynomial-sized formulation, or (3) performing a binary search over the number of points and solving a simpler feasibility or optimization problem at each step. As illustrated by our computational experiments, the polynomial formulation with binary search leads to the most promising results, allowing to optimally solve most instances with up to 25 distance values and 8 solution points.}, author = {Fontoura, L. and Martinelli, R. and Poggi, M. and Vidal, T.}, doi = {10.1007/s10898-017-0579-9}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Fontoura et al/Fontoura et al. - 2018 - The minimum distance superset problem Formulations and algorithms.pdf:pdf}, journal = {Journal of Global Optimization}, number = {1}, pages = {27--53}, title = {{The minimum distance superset problem: Formulations and algorithms}}, url = {https://w1.cirrelt.ca/{~}vidalt/papers/MDSP{\_}ReportFormat.pdf}, volume = {72}, year = {2018} }

The partial digest problem consists in retrieving the positions of a set of points on the real line from their unlabeled pairwise distances. This problem is critical for DNA sequencing, as well as for phase retrieval in X-ray crystallography. When some of the distances are missing, this problem generalizes into a “minimum distance superset problem”, which aims to find a set of points of minimum cardinality such that the multiset of their pairwise distances is a superset of the input. We introduce a quadratic integer programming formulation for the minimum distance superset problem with a pseudo-polynomial number of variables, as well as a polynomial-size integer programming formulation. We investigate three types of solution approaches based on an available integer programming solver: (1) solving a linearization of the pseudo-polynomial-sized formulation, (2) solving the complete polynomial-sized formulation, or (3) performing a binary search over the number of points and solving a simpler feasibility or optimization problem at each step. As illustrated by our computational experiments, the polynomial formulation with binary search leads to the most promising results, allowing to optimally solve most instances with up to 25 distance values and 8 solution points.

Large neighborhood-based metaheuristic and branch-and-price for the pickup and delivery problem with split loads.
Haddad, M.; Martinelli, R.; Vidal, T.; Martins, S.; Ochi, L.; Souza, M.; and Hartl, R.

Paper doi bibtex

*European Journal of Operational Research*, 270(3): 1014–1027. 2018.Paper doi bibtex

@article{Haddad2018, author = {Haddad, M.N. and Martinelli, R. and Vidal, T. and Martins, S. and Ochi, L.S. and Souza, M.J.F. and Hartl, R.F.}, doi = {10.1016/j.ejor.2018.04.017}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Haddad et al/Haddad et al. - 2018 - Large neighborhood-based metaheuristic and branch-and-price for the pickup and delivery problem with split loads.pdf:pdf}, journal = {European Journal of Operational Research}, number = {3}, pages = {1014--1027}, title = {{Large neighborhood-based metaheuristic and branch-and-price for the pickup and delivery problem with split loads}}, url = {https://arxiv.org/pdf/1802.06318.pdf}, volume = {270}, year = {2018} }

Industrial and Tramp Ship Routing Problems: Closing the Gap for Real-Scale Instances.
Homsi, G.; Martinelli, R.; Vidal, T.; and Fagerholt, K.
Technical Report 2018.

Paper bibtex

Paper bibtex

@techreport{Homsi2018, author = {Homsi, G. and Martinelli, R. and Vidal, T. and Fagerholt, K.}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Homsi et al/Homsi et al. - 2018 - Industrial and Tramp Ship Routing Problems Closing the Gap for Real-Scale Instances.pdf:pdf}, title = {{Industrial and Tramp Ship Routing Problems: Closing the Gap for Real-Scale Instances}}, url = {https://arxiv.org/pdf/1809.10584.pdf}, year = {2018} }

Workload equity in vehicle routing problems: A survey and analysis.
Matl, P.; Hartl, R.; and Vidal, T.

Paper bibtex

*Transportation Science*, 52(2): 239–260. 2018.Paper bibtex

@article{Matl2018, author = {Matl, P. and Hartl, R.F. and Vidal, T.}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Matl, Hartl, Vidal/Matl, Hartl, Vidal - 2018 - Workload equity in vehicle routing problems A survey and analysis.pdf:pdf}, journal = {Transportation Science}, mendeley-groups = {VRP-Objectives/1. EQUITY}, number = {2}, pages = {239--260}, title = {{Workload equity in vehicle routing problems: A survey and analysis}}, url = {https://arxiv.org/abs/1605.08565}, volume = {52}, year = {2018} }

On a Fixed-Route Lateral Transhipment Problem with Piecewise Linear Profits.
Romauch, M.; Vidal, T.; and Hartl, R.
Technical Report 2018.

bibtex

bibtex

@techreport{Romauch2018, author = {Romauch, M. and Vidal, T. and Hartl, R.F.}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Romauch, Vidal, Hartl/Romauch, Vidal, Hartl - 2018 - On a Fixed-Route Lateral Transhipment Problem with Piecewise Linear Profits.pdf:pdf}, title = {{On a Fixed-Route Lateral Transhipment Problem with Piecewise Linear Profits}}, year = {2018} }

2017
(4)

A hybrid genetic algorithm with decomposition phases for the unequal area facility layout problem.
Paes, F.; Pessoa, A.; and Vidal, T.

Paper doi bibtex abstract

*European Journal of Operational Research*, 256(3): 742–756. 2017.Paper doi bibtex abstract

@article{Paes2016, abstract = {We address the Unequal-Area Facility-Layout Problem (UA-FLP), which aims to dimension and locate rectangular facilities in an unlimited floor space, without overlap, while minimizing the sum of distances among facilities weighted by “material-handling” flows. We introduce two algorithmic approaches to address this problem: a basic Genetic Algorithm (GA), and a GA combined with a decomposition strategy via partial solution deconstructions and reconstructions. To efficiently decompose the problem, we impose a solution structure where no facility should cross the X or Y axis. Although this restriction can possibly deteriorate the value of the best achievable solution, it also greatly enhances the search capabilities of the method on medium and large problem instances. For most such instances, current exact methods are impracticable. As highlighted by our experiments, the resulting algorithm produces solutions of high quality for the two classic datasets of the literature, improving six out of the eight best known solutions from the first set, with up to 125 facilities, and all medium- and large-scale instances from the second set. For some of the largest instances of the second set, with 90 or 100 facilities, the average solution improvement goes as high as 6 percent or 7 percent when compared to previous algorithms, in less CPU time. We finally introduce additional instances with up to 150 facilities. On this benchmark, the decomposition method provides an average solution improvement with respect to the basic GA of about 9 percent and 1.3 percent on short and long runs, respectively.}, author = {Paes, F.G. and Pessoa, A.A. and Vidal, T.}, doi = {10.1016/j.ejor.2016.07.022}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Paes, Pessoa, Vidal/Paes, Pessoa, Vidal - 2017 - A hybrid genetic algorithm with decomposition phases for the unequal area facility layout problem.pdf:pdf}, journal = {European Journal of Operational Research}, keywords = {Decomposition strategies,Facility layout,Genetic algorithm,Hybrid metaheuristics}, number = {3}, pages = {742--756}, publisher = {Elsevier B.V.}, title = {{A hybrid genetic algorithm with decomposition phases for the unequal area facility layout problem}}, url = {http://linkinghub.elsevier.com/retrieve/pii/S0377221716305598}, volume = {256}, year = {2017} }

We address the Unequal-Area Facility-Layout Problem (UA-FLP), which aims to dimension and locate rectangular facilities in an unlimited floor space, without overlap, while minimizing the sum of distances among facilities weighted by “material-handling” flows. We introduce two algorithmic approaches to address this problem: a basic Genetic Algorithm (GA), and a GA combined with a decomposition strategy via partial solution deconstructions and reconstructions. To efficiently decompose the problem, we impose a solution structure where no facility should cross the X or Y axis. Although this restriction can possibly deteriorate the value of the best achievable solution, it also greatly enhances the search capabilities of the method on medium and large problem instances. For most such instances, current exact methods are impracticable. As highlighted by our experiments, the resulting algorithm produces solutions of high quality for the two classic datasets of the literature, improving six out of the eight best known solutions from the first set, with up to 125 facilities, and all medium- and large-scale instances from the second set. For some of the largest instances of the second set, with 90 or 100 facilities, the average solution improvement goes as high as 6 percent or 7 percent when compared to previous algorithms, in less CPU time. We finally introduce additional instances with up to 150 facilities. On this benchmark, the decomposition method provides an average solution improvement with respect to the basic GA of about 9 percent and 1.3 percent on short and long runs, respectively.

New benchmark instances for the capacitated vehicle routing problem.
Uchoa, E.; Pecin, D.; Pessoa, A.; Poggi, M.; Subramanian, A.; and Vidal, T.

Paper doi bibtex abstract

*European Journal of Operational Research*, 257(3): 845–858. 2017.Paper doi bibtex abstract

@article{Uchoa2017, abstract = {The recent research on the CVRP is being slowed down by the lack of a good set of benchmark instances. The existing sets suff er from at least one of the following drawbacks: (i) became too easy for current algorithms; (ii) are too articial; (iii) are too homogeneous, not covering the wide range of characteristics found in real applications. We propose a new set of instances ranging from 100 to 1000 customers, designed in order to provide a more comprehensive and balanced experimental setting. We report results with state-of-the-art exact and heuristic methods.}, author = {Uchoa, E. and Pecin, D. and Pessoa, A. and Poggi, M. and Subramanian, A. and Vidal, T.}, doi = {10.1016/j.ejor.2016.08.012}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Uchoa et al/Uchoa et al. - 2017 - New benchmark instances for the capacitated vehicle routing problem.pdf:pdf}, journal = {European Journal of Operational Research}, keywords = {benchmark instances,experimental analysis of algorithms,vehicle routing problem}, number = {3}, pages = {845--858}, title = {{New benchmark instances for the capacitated vehicle routing problem}}, url = {http://www.optimization-online.org/DB{\_}FILE/2014/10/4597.pdf}, volume = {257}, year = {2017} }

The recent research on the CVRP is being slowed down by the lack of a good set of benchmark instances. The existing sets suff er from at least one of the following drawbacks: (i) became too easy for current algorithms; (ii) are too articial; (iii) are too homogeneous, not covering the wide range of characteristics found in real applications. We propose a new set of instances ranging from 100 to 1000 customers, designed in order to provide a more comprehensive and balanced experimental setting. We report results with state-of-the-art exact and heuristic methods.

Node, edge, arc routing and turn penalties: Multiple problems – One neighborhood extension.
Vidal, T.

Paper doi bibtex abstract

*Operations Research*, 65(4): 992–1010. 2017.Paper doi bibtex abstract

@article{Vidal2017b, abstract = {This article explores a structural neighborhood decomposition for arc routing problems, in which the decisions about traversal orientations during services are made optimally as part of neighbor evaluation procedures. Using memory structures, bidirectional dynamic programming, and lower bounds, we show that a large neighborhood involving classical moves on the sequences of services along with optimal orientation decisions can be searched in amortized O(1) time per move evaluation instead of O(n) as in previous works. Because of its generality and now-reduced complexity, this approach can be efficiently applied to several variants of arc routing problems, extended into large neighborhoods such as ejection chains, and integrated into two classical metaheuristics. Our computational experiments lead to solutions of high quality on the main benchmark sets for the capacitated arc routing problem (CARP), the mixed capacitated general routing problem (MCGRP), the periodic CARP, the multidepot CARP, and the min-max k-vehicles windy rural postman problem, with a total of 1,528 instances. We also report sensitivity analyses for new MCGRP instances with turn penalties, which are uncommonly challenging yet critical for many practical applications.}, author = {Vidal, T.}, doi = {10.1287/opre.2017.1595}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal/Vidal - 2017 - Node, edge, arc routing and turn penalties Multiple problems -- One neighborhood extension.pdf:pdf}, journal = {Operations Research}, keywords = {arc routing,decomposition,general routing,heuristics,large neighborhood search,local search,service clusters,structural problem,turn penalties}, mendeley-groups = {VRP-Var3-EVAL/Var3-EVAL-ArcRouting/CARP-TurnRestrictions}, number = {4}, pages = {992--1010}, title = {{Node, edge, arc routing and turn penalties: Multiple problems -- One neighborhood extension}}, url = {https://w1.cirrelt.ca/{~}vidalt/papers/NEARP-Vidal-Revision-WP.pdf}, volume = {65}, year = {2017} }

This article explores a structural neighborhood decomposition for arc routing problems, in which the decisions about traversal orientations during services are made optimally as part of neighbor evaluation procedures. Using memory structures, bidirectional dynamic programming, and lower bounds, we show that a large neighborhood involving classical moves on the sequences of services along with optimal orientation decisions can be searched in amortized O(1) time per move evaluation instead of O(n) as in previous works. Because of its generality and now-reduced complexity, this approach can be efficiently applied to several variants of arc routing problems, extended into large neighborhoods such as ejection chains, and integrated into two classical metaheuristics. Our computational experiments lead to solutions of high quality on the main benchmark sets for the capacitated arc routing problem (CARP), the mixed capacitated general routing problem (MCGRP), the periodic CARP, the multidepot CARP, and the min-max k-vehicles windy rural postman problem, with a total of 1,528 instances. We also report sensitivity analyses for new MCGRP instances with turn penalties, which are uncommonly challenging yet critical for many practical applications.

Corrigendum to “Hybrid metaheuristics for the clustered vehicle routing problem [Comput. Oper. Res., 58 (2015): 87–99]”.
Vidal, T.; Battarra, M.; Subramanian, A.; and Erdoǧan, G.

Paper doi bibtex

*Computers & Operations Research*,1–2. 2017.Paper doi bibtex

@article{Vidal2017a, author = {Vidal, T. and Battarra, M. and Subramanian, A. and Erdoǧan, G.}, doi = {10.1016/j.cor.2017.04.003}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal et al/Vidal et al. - 2017 - Corrigendum to “Hybrid metaheuristics for the clustered vehicle routing problem Comput. Oper. Res., 58 (2015) 87–9.pdf:pdf}, journal = {Computers {\&} Operations Research}, pages = {1--2}, title = {{Corrigendum to “Hybrid metaheuristics for the clustered vehicle routing problem [Comput. Oper. Res., 58 (2015): 87–99]”}}, url = {http://linkinghub.elsevier.com/retrieve/pii/S0305054817300849}, year = {2017} }

2016
(4)

A large neighbourhood based heuristic for the two-echelon vehicle routing problem.
Breunig, U.; Schmid, V.; Hartl, R.; and Vidal, T.

Paper doi bibtex abstract

*Computers & Operations Research*, 76: 208–225. 2016.Paper doi bibtex abstract

@article{Breunig2015, abstract = {In this paper, we address two optimisation problems arising in the context of city logistics and two-level transportation systems. The two-echelon vehicle routing problem and the two-echelon location routing problem seek to produce vehicle itineraries to deliver goods to customers, with transits through intermediate facilities. To efficiently solve these problems, we propose a hybrid metaheuristic which combines enumerative local searches with destroy-and-repair principles, as well as some tailored operators to optimise the selections of intermediate facilities. We conduct extensive computational experiments to investigate the contribution of these operators to the search performance, and measure the performance of the method on both problem classes. The proposed algorithm finds the current best known solutions, or better ones, for 95{\%} of the two-echelon vehicle routing problem benchmark instances. Overall, for both problems, it achieves high-quality solutions within short computing times. Finally, for future reference, we resolve inconsistencies between different versions of benchmark instances, document their differences, and provide them all online in a unified format.}, author = {Breunig, U. and Schmid, V. and Hartl, R.H. and Vidal, T.}, doi = {10.1016/j.cor.2016.06.014}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Breunig et al/Breunig et al. - 2016 - A large neighbourhood based heuristic for the two-echelon vehicle routing problem.pdf:pdf}, journal = {Computers {\&} Operations Research}, pages = {208--225}, title = {{A large neighbourhood based heuristic for the two-echelon vehicle routing problem}}, url = {https://arxiv.org/pdf/1505.08003.pdf}, volume = {76}, year = {2016} }

In this paper, we address two optimisation problems arising in the context of city logistics and two-level transportation systems. The two-echelon vehicle routing problem and the two-echelon location routing problem seek to produce vehicle itineraries to deliver goods to customers, with transits through intermediate facilities. To efficiently solve these problems, we propose a hybrid metaheuristic which combines enumerative local searches with destroy-and-repair principles, as well as some tailored operators to optimise the selections of intermediate facilities. We conduct extensive computational experiments to investigate the contribution of these operators to the search performance, and measure the performance of the method on both problem classes. The proposed algorithm finds the current best known solutions, or better ones, for 95% of the two-echelon vehicle routing problem benchmark instances. Overall, for both problems, it achieves high-quality solutions within short computing times. Finally, for future reference, we resolve inconsistencies between different versions of benchmark instances, document their differences, and provide them all online in a unified format.

Technical note: Split algorithm in O(n) for the capacitated vehicle routing problem.
Vidal, T.

Paper doi bibtex abstract

*Computers & Operations Research*, 69: 40–47. 2016.Paper doi bibtex abstract

@article{Vidal2016, abstract = {The Split algorithm is an essential building block of route-first cluster-second heuristics and modern genetic algorithms for vehicle routing problems. The algorithm is used to partition a solution, represented as a giant tour without occurrences of the depot, into separate routes with minimum cost. As highlighted by the recent survey of Prins et al. [18], no less than 70 recent articles use this technique. In the vehicle routing literature, Split is usually assimilated to the search for a shortest path in a directed acyclic graph G and solved in O(nB) using Bellman׳s algorithm, where n is the number of delivery points and B is the average number of feasible routes that start with a given customer in the giant tour. Some linear-time algorithms are also known for this problem as a consequence of a Monge property of G. In this paper, we highlight a stronger property of this graph, leading to a simple alternative algorithm in O(n). Experimentally, we observe that the approach is faster than the classical Split for problem instances of practical size. We also extend the method to deal with a limited fleet and soft capacity constraints.}, author = {Vidal, T.}, doi = {10.1016/j.cor.2015.11.012}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal/Vidal - 2016 - Technical note Split algorithm in O(n) for the capacitated vehicle routing problem.pdf:pdf}, journal = {Computers {\&} Operations Research}, keywords = {Cluster-first route-second heuristic,Large neighborhood search,Split algorithm,Vehicle routing problem,large neighborhood search,vehicle routing problem}, pages = {40--47}, publisher = {Elsevier}, title = {{Technical note: Split algorithm in O(n) for the capacitated vehicle routing problem}}, url = {https://arxiv.org/pdf/1508.02759.pdf}, volume = {69}, year = {2016} }

The Split algorithm is an essential building block of route-first cluster-second heuristics and modern genetic algorithms for vehicle routing problems. The algorithm is used to partition a solution, represented as a giant tour without occurrences of the depot, into separate routes with minimum cost. As highlighted by the recent survey of Prins et al. [18], no less than 70 recent articles use this technique. In the vehicle routing literature, Split is usually assimilated to the search for a shortest path in a directed acyclic graph G and solved in O(nB) using Bellman׳s algorithm, where n is the number of delivery points and B is the average number of feasible routes that start with a given customer in the giant tour. Some linear-time algorithms are also known for this problem as a consequence of a Monge property of G. In this paper, we highlight a stronger property of this graph, leading to a simple alternative algorithm in O(n). Experimentally, we observe that the approach is faster than the classical Split for problem instances of practical size. We also extend the method to deal with a limited fleet and soft capacity constraints.

A decomposition algorithm for nested resource allocation problems.
Vidal, T.; Jaillet, P.; and Maculan, N.

Paper doi bibtex abstract

*SIAM Journal on Optimization*, 26(2): 1322–1340. 2016.Paper doi bibtex abstract

@article{Vidal2014a, abstract = {We propose an exact polynomial algorithm for a resource allocation problem with convex costs and constraints on partial sums of resource consumptions, in the presence of either continuous or integer variables. No assumption of strict convexity or differentiability is needed. The method solves a hierarchy of resource allocation subproblems, whose solutions are used to convert constraints on sums of resources into bounds for separate variables at higher levels. The resulting time complexity for the integer problem is {\$}O(n \backslashlog m \backslashlog (B/n)){\$}, and the complexity of obtaining an {\$}\backslashepsilon{\$}-approximate solution for the continuous case is {\$}O(n \backslashlog m \backslashlog (B/\backslashepsilon)){\$}, {\$}n{\$} being the number of variables, {\$}m{\$} the number of ascending constraints (such that {\$}m {\textless} n{\$}), {\$}\backslashepsilon{\$} a desired precision, and {\$}B{\$} the total resource. This algorithm attains the best-known complexity when {\$}m = n{\$}, and improves it when {\$}\backslashlog m = o(\backslashlog n){\$}. Extensive experimental analyses are conducted with four recent algorithms on various continuous problems issued from theory and practice. The proposed method achieves a higher performance than previous algorithms, addressing all problems with up to one million variables in less than one minute on a modern computer.}, author = {Vidal, T. and Jaillet, P. and Maculan, N.}, doi = {10.1137/140965119}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal, Jaillet, Maculan/Vidal, Jaillet, Maculan - 2016 - A decomposition algorithm for nested resource allocation problems.pdf:pdf}, journal = {SIAM Journal on Optimization}, number = {2}, pages = {1322--1340}, title = {{A decomposition algorithm for nested resource allocation problems}}, url = {https://arxiv.org/pdf/1404.6694.pdf}, volume = {26}, year = {2016} }

We propose an exact polynomial algorithm for a resource allocation problem with convex costs and constraints on partial sums of resource consumptions, in the presence of either continuous or integer variables. No assumption of strict convexity or differentiability is needed. The method solves a hierarchy of resource allocation subproblems, whose solutions are used to convert constraints on sums of resources into bounds for separate variables at higher levels. The resulting time complexity for the integer problem is \$}O(n \backslashlog m \backslashlog (B/n)){\$, and the complexity of obtaining an \$}\backslashepsilon{\$-approximate solution for the continuous case is \$}O(n \backslashlog m \backslashlog (B/\backslashepsilon)){\$, \$}n{\$ being the number of variables, \$}m{\$ the number of ascending constraints (such that \$}m {\textless} n{\$), \$}\backslashepsilon{\$ a desired precision, and \$}B{\$ the total resource. This algorithm attains the best-known complexity when \$}m = n{\$, and improves it when \$}\backslashlog m = o(\backslashlog n){\$. Extensive experimental analyses are conducted with four recent algorithms on various continuous problems issued from theory and practice. The proposed method achieves a higher performance than previous algorithms, addressing all problems with up to one million variables in less than one minute on a modern computer.

Large neighborhoods with implicit customer selection for vehicle routing problems with profits.
Vidal, T.; Maculan, N.; Ochi, L.; and Penna, P.

Paper doi bibtex abstract

*Transportation Science*, 50(2): 720–734. 2016.Paper doi bibtex abstract

@article{Vidal2014, abstract = {We consider several vehicle routing problems (VRP) with profits, which seek to select a subset of customers, each one being associated with a profit, and to design service itineraries. When the sum of profits is maximized under distance constraints, the problem is usually called the team orienteering problem. The capacitated profitable tour problem seeks to maximize profits minus travel costs under capacity constraints. Finally, in the VRP with a private fleet and common carrier, some customers can be delegated to an external carrier subject to a cost. Three families of combined decisions must be taken: customer's selection, assignment to vehicles, and sequencing of deliveries for each route. We propose a new neighborhood search for these problems, which explores an exponential number of solutions in pseudo-polynomial time. The search is conducted with standard VRP neighborhoods on an exhaustive solution representation, visiting all customers. Since visiting all customers is usually infeasible or suboptimal, an efficient select algorithm, based on resource constrained shortest paths, is repeatedly used on any new route to find the optimal subsequence of visits to customers. The good performance of these neighborhood structures is demonstrated by extensive computational experiments with a local search, an iterated local search, and a hybrid genetic algorithm. Intriguingly, even a local-improvement method to the first local optimum of this neighborhood achieves an average gap of 0.09{\%} on classic team orienteering benchmark instances, rivaling with the current state-of-the-art metaheuristics. Promising research avenues on hybridizations with more standard routing neighborhoods are also open.}, author = {Vidal, T. and Maculan, N. and Ochi, L.S. and Penna, P.H.V.}, doi = {10.1287/trsc.2015.0584}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal et al/Vidal et al. - 2016 - Large neighborhoods with implicit customer selection for vehicle routing problems with profits.pdf:pdf}, journal = {Transportation Science}, number = {2}, pages = {720--734}, title = {{Large neighborhoods with implicit customer selection for vehicle routing problems with profits}}, url = {https://arxiv.org/pdf/1401.3794.pdf}, volume = {50}, year = {2016} }

We consider several vehicle routing problems (VRP) with profits, which seek to select a subset of customers, each one being associated with a profit, and to design service itineraries. When the sum of profits is maximized under distance constraints, the problem is usually called the team orienteering problem. The capacitated profitable tour problem seeks to maximize profits minus travel costs under capacity constraints. Finally, in the VRP with a private fleet and common carrier, some customers can be delegated to an external carrier subject to a cost. Three families of combined decisions must be taken: customer's selection, assignment to vehicles, and sequencing of deliveries for each route. We propose a new neighborhood search for these problems, which explores an exponential number of solutions in pseudo-polynomial time. The search is conducted with standard VRP neighborhoods on an exhaustive solution representation, visiting all customers. Since visiting all customers is usually infeasible or suboptimal, an efficient select algorithm, based on resource constrained shortest paths, is repeatedly used on any new route to find the optimal subsequence of visits to customers. The good performance of these neighborhood structures is demonstrated by extensive computational experiments with a local search, an iterated local search, and a hybrid genetic algorithm. Intriguingly, even a local-improvement method to the first local optimum of this neighborhood achieves an average gap of 0.09% on classic team orienteering benchmark instances, rivaling with the current state-of-the-art metaheuristics. Promising research avenues on hybridizations with more standard routing neighborhoods are also open.

2015
(7)

Solution integration in combinatorial optimization with applications to cooperative search and rich vehicle routing.
El Hachemi, N.; Crainic, T.; Lahrichi, N.; Rei, W.; and Vidal, T.

Paper doi bibtex abstract

*Journal of Heuristics*, 21(5): 663–685. 2015.Paper doi bibtex abstract

@article{ElHachemi2015, abstract = {Problem decomposition requires the ability to recombine partial solutions. This recombination task, which we call integration, is a fundamental feature of many methods, both those based on mathematical formulations such as Dantzig–Wolfe or Benders and those based on heuristics. Integration may be implicit in mathematical decompositions, but in heuristics this critical task is usually managed by ad-hoc operators, e.g., operators that combine decisions and heuristic adjustments to manage incompatibilities. In this paper, we propose a general framework for integration, which is viewed as a problem in itself with well-defined objectives and constraints. Four different mechanisms are proposed, based on well-known concepts from the literature such as constraining or giving incentives to particular characteristics of partial solutions. We perform computational experiments on the multi-depot periodic vehicle routing problem to compare the various integration approaches. The strategy that places incentives on selected solution characteristics rather than imposing constraints seems to yield the best results in the context of a cooperative search for this problem.}, author = {{El Hachemi}, N. and Crainic, T.G. and Lahrichi, N. and Rei, W. and Vidal, T.}, doi = {10.1007/s10732-015-9296-z}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/El Hachemi et al/El Hachemi et al. - 2015 - Solution integration in combinatorial optimization with applications to cooperative search and rich vehicle r.pdf:pdf}, journal = {Journal of Heuristics}, number = {5}, pages = {663--685}, title = {{Solution integration in combinatorial optimization with applications to cooperative search and rich vehicle routing}}, url = {https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2014-40.pdf}, volume = {21}, year = {2015} }

Problem decomposition requires the ability to recombine partial solutions. This recombination task, which we call integration, is a fundamental feature of many methods, both those based on mathematical formulations such as Dantzig–Wolfe or Benders and those based on heuristics. Integration may be implicit in mathematical decompositions, but in heuristics this critical task is usually managed by ad-hoc operators, e.g., operators that combine decisions and heuristic adjustments to manage incompatibilities. In this paper, we propose a general framework for integration, which is viewed as a problem in itself with well-defined objectives and constraints. Four different mechanisms are proposed, based on well-known concepts from the literature such as constraining or giving incentives to particular characteristics of partial solutions. We perform computational experiments on the multi-depot periodic vehicle routing problem to compare the various integration approaches. The strategy that places incentives on selected solution characteristics rather than imposing constraints seems to yield the best results in the context of a cooperative search for this problem.

A speed and departure time optimization algorithm for the pollution-routing problem.
Kramer, R.; Maculan, N.; Subramanian, A.; and Vidal, T.

Paper doi bibtex abstract

*European Journal of Operational Research*, 247(3): 782–787. 2015.Paper doi bibtex abstract

@article{Kramer2015a, abstract = {We propose a new speed and departure time optimization algorithm for the pollution-routing problem (PRP), which runs in quadratic time and returns an optimal schedule. This algorithm is embedded into an iterated local search-based metaheuristic to achieve a combined speed, scheduling and routing optimization. The start of the working day is set as a decision variable for individual routes, thus enabling a better assignment of human resources to required demands. Some routes that were evaluated as unprofitable can now appear as viable candidates later in the day, leading to a larger search space and further opportunities of distance optimization via better service consolidation. Extensive computational experiments on available PRP benchmark instances demonstrate the good performance of the algorithm. The flexible departure times from the depot contribute to reduce the operational costs by 8.36{\%} on the considered instances.}, author = {Kramer, R. and Maculan, N. and Subramanian, A. and Vidal, T.}, doi = {10.1016/j.ejor.2015.06.037}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Kramer et al/Kramer et al. - 2015 - A speed and departure time optimization algorithm for the pollution-routing problem.pdf:pdf}, journal = {European Journal of Operational Research}, mendeley-groups = {VRP-Objectives/6. EXTERNALITIES/Pollution/Pollution-Routing,VRP-Objectives/6. EXTERNALITIES/Pollution}, number = {3}, pages = {782--787}, title = {{A speed and departure time optimization algorithm for the pollution-routing problem}}, url = {https://arxiv.org/pdf/1501.05354.pdf}, volume = {247}, year = {2015} }

We propose a new speed and departure time optimization algorithm for the pollution-routing problem (PRP), which runs in quadratic time and returns an optimal schedule. This algorithm is embedded into an iterated local search-based metaheuristic to achieve a combined speed, scheduling and routing optimization. The start of the working day is set as a decision variable for individual routes, thus enabling a better assignment of human resources to required demands. Some routes that were evaluated as unprofitable can now appear as viable candidates later in the day, leading to a larger search space and further opportunities of distance optimization via better service consolidation. Extensive computational experiments on available PRP benchmark instances demonstrate the good performance of the algorithm. The flexible departure times from the depot contribute to reduce the operational costs by 8.36% on the considered instances.

A matheuristic approach for the pollution-routing problem.
Kramer, R.; Subramanian, A.; Vidal, T.; and Cabral, L.

Paper doi bibtex abstract

*European Journal of Operational Research*, 243(2): 523–539. 2015.Paper doi bibtex abstract

@article{Kramer2015, abstract = {This paper deals with the Pollution-Routing Problem (PRP), a Vehicle Routing Problem (VRP) with environmental considerations, recently introduced in the literature by Bektaş and Laporte (2011) [Transportation Research Part B: Methodological 45 (8), 1232–1250]. The objective is to minimize operational and environmental costs while respecting capacity constraints and service time windows. Costs are based on driver wages and fuel consumption, which depends on many factors, such as travel distance and vehicle load. The vehicle speeds are considered as decision variables. They complement routing decisions, impacting the total cost, the travel time between locations, and thus the set of feasible routes. We propose a method which combines a local search-based metaheuristic with an integer programming approach over a set covering formulation and a recursive speed-optimization algorithm. This hybridization enables to integrate more tightly route and speed decisions. Moreover, two other “green” VRP variants, the Fuel Consumption VRP (FCVRP) and the Energy Minimizing VRP (EMVRP), are addressed, as well as the VRP with time windows (VRPTW) with distance minimization. The proposed method compares very favorably with previous algorithms from the literature, and new improved solutions are reported for all considered problems.}, author = {Kramer, R. and Subramanian, A. and Vidal, T. and Cabral, L.A.F.}, doi = {10.1016/j.ejor.2014.12.009}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Kramer et al/Kramer et al. - 2015 - A matheuristic approach for the pollution-routing problem.pdf:pdf}, journal = {European Journal of Operational Research}, mendeley-groups = {VRP-Objectives/6. EXTERNALITIES/Pollution/Pollution-Routing,VRP-Objectives/6. EXTERNALITIES/Pollution}, number = {2}, pages = {523--539}, title = {{A matheuristic approach for the pollution-routing problem}}, url = {https://arxiv.org/pdf/1404.4895.pdf}, volume = {243}, year = {2015} }

This paper deals with the Pollution-Routing Problem (PRP), a Vehicle Routing Problem (VRP) with environmental considerations, recently introduced in the literature by Bektaş and Laporte (2011) [Transportation Research Part B: Methodological 45 (8), 1232–1250]. The objective is to minimize operational and environmental costs while respecting capacity constraints and service time windows. Costs are based on driver wages and fuel consumption, which depends on many factors, such as travel distance and vehicle load. The vehicle speeds are considered as decision variables. They complement routing decisions, impacting the total cost, the travel time between locations, and thus the set of feasible routes. We propose a method which combines a local search-based metaheuristic with an integer programming approach over a set covering formulation and a recursive speed-optimization algorithm. This hybridization enables to integrate more tightly route and speed decisions. Moreover, two other “green” VRP variants, the Fuel Consumption VRP (FCVRP) and the Energy Minimizing VRP (EMVRP), are addressed, as well as the VRP with time windows (VRPTW) with distance minimization. The proposed method compares very favorably with previous algorithms from the literature, and new improved solutions are reported for all considered problems.

An integrative cooperative search framework for multi-decision-attribute combinatorial optimization: Application to the MDPVRP.
Lahrichi, N.; Crainic, T.; Gendreau, M.; Rei, W.; Crisan, G.; and Vidal, T.

Paper doi bibtex abstract

*European Journal of Operational Research*, 246(2): 400–412. 2015.Paper doi bibtex abstract

@article{Lahrichi2015, abstract = {We introduce the integrative cooperative search method (ICS), a multi-thread cooperative search method for multi-attribute combinatorial optimization problems. ICS musters the combined capabilities of a number of independent exact or meta-heuristic solution methods. A number of these methods work on sub-problems defined by suitably selected subsets of decision-set attributes of the problem, while others combine the resulting partial solutions into complete ones and, eventually, improve them. All these methods cooperate through an adaptive search-guidance mechanism, using the central-memory cooperative search paradigm. Extensive numerical experiments explore the behavior of ICS and its interest through an application to the multi-depot, periodic vehicle routing problem, for which ICS improves the results of the current state-of-the-art methods.}, author = {Lahrichi, N. and Crainic, T.G. and Gendreau, M. and Rei, W. and Crisan, G.C. and Vidal, T.}, doi = {10.1016/j.ejor.2015.05.}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Lahrichi et al/Lahrichi et al. - 2015 - An integrative cooperative search framework for multi-decision-attribute combinatorial optimization Application.pdf:pdf}, journal = {European Journal of Operational Research}, keywords = {Decision-set decomposition,Integrative cooperative search,Meta-heuristics,Multi-attribute combinatorial optimization,Multi-depot periodic vehicle routing,integrative cooperative search,multi-attribute combinatorial optimization}, number = {2}, pages = {400--412}, title = {{An integrative cooperative search framework for multi-decision-attribute combinatorial optimization: Application to the MDPVRP}}, url = {https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2012-42.pdf}, volume = {246}, year = {2015} }

We introduce the integrative cooperative search method (ICS), a multi-thread cooperative search method for multi-attribute combinatorial optimization problems. ICS musters the combined capabilities of a number of independent exact or meta-heuristic solution methods. A number of these methods work on sub-problems defined by suitably selected subsets of decision-set attributes of the problem, while others combine the resulting partial solutions into complete ones and, eventually, improve them. All these methods cooperate through an adaptive search-guidance mechanism, using the central-memory cooperative search paradigm. Extensive numerical experiments explore the behavior of ICS and its interest through an application to the multi-depot, periodic vehicle routing problem, for which ICS improves the results of the current state-of-the-art methods.

Hybrid metaheuristics for the clustered vehicle routing problem.
Vidal, T.; Battarra, M.; Subramanian, A.; and Erdogan, G.

Paper doi bibtex abstract

*Computers & Operations Research*, 58(1): 87–99. 2015.Paper doi bibtex abstract

@article{Vidal2014b, abstract = {The Clustered Vehicle Routing Problem (CluVRP) is a variant of the Capacitated Vehicle Routing Problem in which customers are grouped into clusters. Each cluster has to be visited once, and a vehicle entering a cluster cannot leave it until all customers have been visited. This paper presents two alternative hybrid metaheuristic algorithms for the CluVRP. The first algorithm is based on an Iterated Local Search algorithm, in which only feasible solutions are explored and problem-specific local search moves are utilized. The second algorithm is a hybrid genetic search, for which the shortest Hamiltonian path between each pair of vertices within each cluster should be precomputed. Using this information, a sequence of clusters can be used as a solution representation and large neighborhoods can be efficiently explored, by means of bi-directional dynamic programming, sequence concatenation, and appropriate data structures. Extensive computational experiments are performed on benchmark instances from the literature, as well as new large scale instances. Recommendations on the choice of algorithm are provided, based on average cluster size.}, author = {Vidal, T. and Battarra, M. and Subramanian, A. and Erdogan, G.}, doi = {10.1016/j.cor.2014.10.019}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal et al/Vidal et al. - 2015 - Hybrid metaheuristics for the clustered vehicle routing problem.pdf:pdf}, journal = {Computers {\&} Operations Research}, mendeley-groups = {Metaheuristics/Decompositions}, number = {1}, pages = {87--99}, title = {{Hybrid metaheuristics for the clustered vehicle routing problem}}, url = {https://arxiv.org/pdf/1404.6696.pdf}, volume = {58}, year = {2015} }

The Clustered Vehicle Routing Problem (CluVRP) is a variant of the Capacitated Vehicle Routing Problem in which customers are grouped into clusters. Each cluster has to be visited once, and a vehicle entering a cluster cannot leave it until all customers have been visited. This paper presents two alternative hybrid metaheuristic algorithms for the CluVRP. The first algorithm is based on an Iterated Local Search algorithm, in which only feasible solutions are explored and problem-specific local search moves are utilized. The second algorithm is a hybrid genetic search, for which the shortest Hamiltonian path between each pair of vertices within each cluster should be precomputed. Using this information, a sequence of clusters can be used as a solution representation and large neighborhoods can be efficiently explored, by means of bi-directional dynamic programming, sequence concatenation, and appropriate data structures. Extensive computational experiments are performed on benchmark instances from the literature, as well as new large scale instances. Recommendations on the choice of algorithm are provided, based on average cluster size.

Time-window relaxations in vehicle routing heuristics.
Vidal, T.; Crainic, T.; Gendreau, M.; and Prins, C.

Paper doi bibtex abstract

*Journal of Heuristics*, 21(3): 329–358. 2015.Paper doi bibtex abstract

@article{Vidal2013a, abstract = {The contribution of infeasible solutions in heuristic searches for vehicle routing problems (VRP) is not a subject of consensus in the metaheuristics community. Infeasible solutions may allow transitioning between structurally different feasible solutions, thus enhancing the search, but they also lead to more complex move-evaluation procedures and wider search spaces. This paper introduces an experimental assessment of the impact of infeasible solutions on heuristic searches, through various empirical studies on local improvement procedures, iterated local searches, and hybrid genetic algorithms for the VRP with time windows and other related variants with fleet mix, backhauls, and multiple periods. Four relaxation schemes are considered, allowing penalized late arrivals to customers, early and late arrivals, returns in time, or a flexible travel time relaxation. For all considered problems and methods, our experiments demonstrate the significant positive impact of penalized infeasible solution. Differences can also be observed between individual relaxation schemes. The “returns in time” and “flexible travel time” relaxations appear as the best options in terms of solution quality, CPU time, and scalability.}, author = {Vidal, T. and Crainic, T.G. and Gendreau, M. and Prins, C.}, doi = {10.1007/s10732-014-9273-y}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal et al/Vidal et al. - 2015 - Time-window relaxations in vehicle routing heuristics.pdf:pdf}, journal = {Journal of Heuristics}, number = {3}, pages = {329--358}, title = {{Time-window relaxations in vehicle routing heuristics}}, url = {https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2013-43.pdf}, volume = {21}, year = {2015} }

The contribution of infeasible solutions in heuristic searches for vehicle routing problems (VRP) is not a subject of consensus in the metaheuristics community. Infeasible solutions may allow transitioning between structurally different feasible solutions, thus enhancing the search, but they also lead to more complex move-evaluation procedures and wider search spaces. This paper introduces an experimental assessment of the impact of infeasible solutions on heuristic searches, through various empirical studies on local improvement procedures, iterated local searches, and hybrid genetic algorithms for the VRP with time windows and other related variants with fleet mix, backhauls, and multiple periods. Four relaxation schemes are considered, allowing penalized late arrivals to customers, early and late arrivals, returns in time, or a flexible travel time relaxation. For all considered problems and methods, our experiments demonstrate the significant positive impact of penalized infeasible solution. Differences can also be observed between individual relaxation schemes. The “returns in time” and “flexible travel time” relaxations appear as the best options in terms of solution quality, CPU time, and scalability.

Timing problems and algorithms: Time decisions for sequences of activities.
Vidal, T.; Crainic, T.; Gendreau, M.; and Prins, C.

Paper doi bibtex abstract

*Networks*, 65(2): 102–128. 2015.Paper doi bibtex abstract

@article{Vidal2015b, abstract = {Timing problems involve the choice of task execution dates within a predetermined processing sequence, and under various additional constraints or objectives such as time windows, time-dependent costs, or flexible processing times, among others. Their efficient resolution is critical in branch and bound and neighborhood search methods for vehicle routing, project and machine scheduling, as well as in various applications in network optimization, resource allocation, and statistical inference. Timing-related problems have been studied for years, yet research on this subject suffers from a lack of consensus, and most knowledge is scattered among operations research and applied mathematics domains. This article introduces a classification of timing problems and features, as well as a unifying multidisciplinary analysis of timing algorithms. In relation to frequent application cases within branching schemes or neighborhood searches, the efficient resolution of series of similar timing subproblems is also analyzed. A dedicated formalism of reoptimization “by concatenation” is introduced to that extent. The knowledge developed through this analysis is valuable for modeling and algorithmic design, for a wide range of combinatorial optimization problems with time characteristics, including rich vehicle routing settings and emerging nonregular scheduling applications, among others.}, author = {Vidal, T. and Crainic, T.G. and Gendreau, M. and Prins, C.}, doi = {10.1002/net.21587}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal et al/Vidal et al. - 2015 - Timing problems and algorithms Time decisions for sequences of activities.pdf:pdf}, journal = {Networks}, number = {2}, pages = {102--128}, title = {{Timing problems and algorithms: Time decisions for sequences of activities}}, url = {https://w1.cirrelt.ca/{~}vidalt/papers/Timing-Problems-Final.pdf}, volume = {65}, year = {2015} }

Timing problems involve the choice of task execution dates within a predetermined processing sequence, and under various additional constraints or objectives such as time windows, time-dependent costs, or flexible processing times, among others. Their efficient resolution is critical in branch and bound and neighborhood search methods for vehicle routing, project and machine scheduling, as well as in various applications in network optimization, resource allocation, and statistical inference. Timing-related problems have been studied for years, yet research on this subject suffers from a lack of consensus, and most knowledge is scattered among operations research and applied mathematics domains. This article introduces a classification of timing problems and features, as well as a unifying multidisciplinary analysis of timing algorithms. In relation to frequent application cases within branching schemes or neighborhood searches, the efficient resolution of series of similar timing subproblems is also analyzed. A dedicated formalism of reoptimization “by concatenation” is introduced to that extent. The knowledge developed through this analysis is valuable for modeling and algorithmic design, for a wide range of combinatorial optimization problems with time characteristics, including rich vehicle routing settings and emerging nonregular scheduling applications, among others.

2014
(6)

A memetic algorithm for the multi trip vehicle routing problem.
Cattaruzza, D.; Absi, N.; Feillet, D.; and Vidal, T.

Paper doi bibtex abstract 7 downloads

*European Journal of Operational Research*, 236(3): 833–848. 2014.Paper doi bibtex abstract 7 downloads

@article{Cattaruzza2012, abstract = {We consider the Multi Trip Vehicle Routing Problem, in which a set of geographically scattered customers have to be served by a fleet of vehicles. Each vehicle can perform several trips during the working day. The objective is to minimize the total travel time while respecting temporal and capacity constraints. The problem is particularly interesting in the city logistics context, where customers are located in city centers. Road and law restrictions favor the use of small capacity vehicles to perform deliveries. This leads to trips much briefer than the working day. A vehicle can then go back to the depot and be re-loaded before starting another service trip. We propose an hybrid genetic algorithm for the problem. Especially, we introduce a new local search operator based on the combination of standard VRP moves and swaps between trips. Our procedure is compared with those in the literature and it outperforms previous algorithms with respect to average solution quality. Moreover, a new feasible solution and many best known solutions are found.}, author = {Cattaruzza, D. and Absi, N. and Feillet, D. and Vidal, T.}, doi = {10.1016/j.ejor.2013.06.012}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Cattaruzza et al/Cattaruzza et al. - 2014 - A memetic algorithm for the multi trip vehicle routing problem.pdf:pdf}, journal = {European Journal of Operational Research}, number = {3}, pages = {833--848}, title = {{A memetic algorithm for the multi trip vehicle routing problem}}, url = {https://w1.cirrelt.ca/{~}vidalt/papers/WP{\_}EMSE{\_}CMP-SFL{\_}2012-1.pdf}, volume = {236}, year = {2014} }

We consider the Multi Trip Vehicle Routing Problem, in which a set of geographically scattered customers have to be served by a fleet of vehicles. Each vehicle can perform several trips during the working day. The objective is to minimize the total travel time while respecting temporal and capacity constraints. The problem is particularly interesting in the city logistics context, where customers are located in city centers. Road and law restrictions favor the use of small capacity vehicles to perform deliveries. This leads to trips much briefer than the working day. A vehicle can then go back to the depot and be re-loaded before starting another service trip. We propose an hybrid genetic algorithm for the problem. Especially, we introduce a new local search operator based on the combination of standard VRP moves and swaps between trips. Our procedure is compared with those in the literature and it outperforms previous algorithms with respect to average solution quality. Moreover, a new feasible solution and many best known solutions are found.

Hours of service regulations in road freight transport: An optimization-based international assessment.
Goel, A.; and Vidal, T.

Paper doi bibtex abstract

*Transportation Science*, 48(3): 391–412. 2014.Paper doi bibtex abstract

@article{Goel2012, abstract = {Driver fatigue is internationally recognized as a significant factor in approximately 15{\%}–20{\%} of commercial road transport crashes. In their efforts to increase road safety and improve working conditions of truck drivers, governments worldwide are enforcing stricter limits on the amount of working and driving time without rest. This paper describes an effective optimization algorithm for minimizing transportation costs for a fleet of vehicles considering business hours of customers and hours of service regulations. The algorithm combines the exploration capacities of population-based metaheuristics, the quick improvement abilities of local search, with forward labeling procedures for checking compliance with complex hours of service regulations. Several speed-up techniques are proposed to achieve an overall efficient approach. The proposed approach is used to assess the impact of different hours of service regulations from a carrier-centric point of view. Extensive computational experiments for various sets of regulations in the United States, Canada, the European Union, and Australia are conducted to provide an international assessment of the impact of different rules on transportation costs and accident risks. Our experiments demonstrate that European Union rules lead to the highest safety, whereas Canadian regulations are the most competitive in terms of economic efficiency. Australian regulations appear to have unnecessarily high risk rates with respect to operating costs. The recent rule change in the United States reduces accident risk rates with a moderate increase in operating costs}, author = {Goel, A. and Vidal, T.}, doi = {10.1287/trsc.2013.0477}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Goel, Vidal/Goel, Vidal - 2014 - Hours of service regulations in road freight transport An optimization-based international assessment.pdf:pdf}, journal = {Transportation Science}, number = {3}, pages = {391--412}, title = {{Hours of service regulations in road freight transport: An optimization-based international assessment}}, url = {https://papers.ssrn.com/sol3/papers.cfm?abstract{\_}id=2057556}, volume = {48}, year = {2014} }

Driver fatigue is internationally recognized as a significant factor in approximately 15%–20% of commercial road transport crashes. In their efforts to increase road safety and improve working conditions of truck drivers, governments worldwide are enforcing stricter limits on the amount of working and driving time without rest. This paper describes an effective optimization algorithm for minimizing transportation costs for a fleet of vehicles considering business hours of customers and hours of service regulations. The algorithm combines the exploration capacities of population-based metaheuristics, the quick improvement abilities of local search, with forward labeling procedures for checking compliance with complex hours of service regulations. Several speed-up techniques are proposed to achieve an overall efficient approach. The proposed approach is used to assess the impact of different hours of service regulations from a carrier-centric point of view. Extensive computational experiments for various sets of regulations in the United States, Canada, the European Union, and Australia are conducted to provide an international assessment of the impact of different rules on transportation costs and accident risks. Our experiments demonstrate that European Union rules lead to the highest safety, whereas Canadian regulations are the most competitive in terms of economic efficiency. Australian regulations appear to have unnecessarily high risk rates with respect to operating costs. The recent rule change in the United States reduces accident risk rates with a moderate increase in operating costs

Heuristics for the vehicle routing problem.
Laporte, G.; Ropke, S.; and Vidal, T.
In Toth, P.; and Vigo, D., editor(s),

Paper doi bibtex abstract

*Vehicle Routing: Problems, Methods, and Applications*, 4, pages 87–116. Society for Industrial and Applied Mathematics, 2014.Paper doi bibtex abstract

@incollection{Laporte2014a, abstract = {In recent years, several sophisticated mathematical programming decomposition algorithms have been put forward for the solution of the VRP. Yet, despite this effort, only relatively small instances involving around 100 customers can be solved optimally, and the variance of computing times is high. However, instances encountered in real-life settings are sometimes large and must be solved quickly within predictable times, which means that efficient heuristics are required in practice. Also, because the exact problem definition varies from one setting to another, it becomes necessary to develop heuristics that are sufficiently flexible to handle a variety of objectives and side constraints. These concerns are clearly reflected in the algorithms developed over the past few years. This chapter provides an overview of heuristics for the VRP, with an emphasis on recent results.}, annote = {There is a typo in the ACO section, it should be a product, not a substraction.}, author = {Laporte, G. and Ropke, S. and Vidal, T.}, booktitle = {Vehicle Routing: Problems, Methods, and Applications}, chapter = {4}, doi = {10.1137/1.9781611973594.ch4}, editor = {Toth, P. and Vigo, D.}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Laporte, Ropke, Vidal/Laporte, Ropke, Vidal - 2014 - Heuristics for the vehicle routing problem.pdf:pdf}, mendeley-groups = {Metaheuristics/Decompositions,VRP/Surveys}, pages = {87--116}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Heuristics for the vehicle routing problem}}, url = {https://doi.org/10.1137/1.9781611973594.ch4}, year = {2014} }

In recent years, several sophisticated mathematical programming decomposition algorithms have been put forward for the solution of the VRP. Yet, despite this effort, only relatively small instances involving around 100 customers can be solved optimally, and the variance of computing times is high. However, instances encountered in real-life settings are sometimes large and must be solved quickly within predictable times, which means that efficient heuristics are required in practice. Also, because the exact problem definition varies from one setting to another, it becomes necessary to develop heuristics that are sufficiently flexible to handle a variety of objectives and side constraints. These concerns are clearly reflected in the algorithms developed over the past few years. This chapter provides an overview of heuristics for the VRP, with an emphasis on recent results.

Efficient heuristics for the workover rig routing problem with a heterogeneous fleet and a finite horizon.
Ribeiro, G.; Desaulniers, G.; Desrosiers, J.; Vidal, T.; and Vieira, B.

Paper doi bibtex abstract

*Journal of Heuristics*, 20(6): 677–708. 2014.Paper doi bibtex abstract

@article{Ribeiro2014, abstract = {Onshore oil fields may contain hundreds of wells that use sophisticated and complex equipments. These equipments need regular maintenance to keep the wells at maximum productivity. When the productivity of a well decreases, a specially-equipped vehicle called a workover rig must visit this well to restore its full productivity. Given a heterogeneous fleet of workover rigs and a set of wells requiring maintenance, the workover rig routing problem (WRRP) consists of finding rig routes that minimize the total production loss of the wells over a finite horizon. The wells have different loss rates, need different services, and may not be serviced within the horizon. On the other hand, the number of available workover rigs is limited, they have different initial positions, and they do not have the same equipments. This paper presents and compares four heuristics for the WRRP: an existing variable neighborhood search heuristic, a branch-price-and-cut heuristic, an adaptive large neighborhood search heuristic, and a hybrid genetic algorithm. These heuristics are tested on practical-sized instances involving up to 300 wells, 10 rigs on a 350-period horizon. Our computational results indicate that the hybrid genetic algorithm outperforms the other heuristics on average and in most cases.}, author = {Ribeiro, G.M. and Desaulniers, G. and Desrosiers, J. and Vidal, T. and Vieira, B.S.}, doi = {10.1007/s10732-014-9262-1}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Ribeiro et al/Ribeiro et al. - 2014 - Efficient heuristics for the workover rig routing problem with a heterogeneous fleet and a finite horizon.pdf:pdf}, journal = {Journal of Heuristics}, number = {6}, pages = {677--708}, title = {{Efficient heuristics for the workover rig routing problem with a heterogeneous fleet and a finite horizon}}, url = {https://dspace.mit.edu/openaccess-disseminate/1721.1/103514}, volume = {20}, year = {2014} }

Onshore oil fields may contain hundreds of wells that use sophisticated and complex equipments. These equipments need regular maintenance to keep the wells at maximum productivity. When the productivity of a well decreases, a specially-equipped vehicle called a workover rig must visit this well to restore its full productivity. Given a heterogeneous fleet of workover rigs and a set of wells requiring maintenance, the workover rig routing problem (WRRP) consists of finding rig routes that minimize the total production loss of the wells over a finite horizon. The wells have different loss rates, need different services, and may not be serviced within the horizon. On the other hand, the number of available workover rigs is limited, they have different initial positions, and they do not have the same equipments. This paper presents and compares four heuristics for the WRRP: an existing variable neighborhood search heuristic, a branch-price-and-cut heuristic, an adaptive large neighborhood search heuristic, and a hybrid genetic algorithm. These heuristics are tested on practical-sized instances involving up to 300 wells, 10 rigs on a 350-period horizon. Our computational results indicate that the hybrid genetic algorithm outperforms the other heuristics on average and in most cases.

Implicit depot assignments and rotations in vehicle routing heuristics.
Vidal, T.; Crainic, T.; Gendreau, M.; and Prins, C.

Paper doi bibtex abstract 2 downloads

*European Journal of Operational Research*, 237(1): 15–28. 2014.Paper doi bibtex abstract 2 downloads

@article{Vidal2012e, abstract = {Vehicle routing variants with multiple depots and mixed fleet present intricate combinatorial aspects related to sequencing choices, vehicle type choices, depot choices, and depots positioning. This paper introduces a dynamic programming methodology for efficiently evaluating compound neighborhoods combining sequence-based moves with an optimal choice of vehicle and depot, and an optimal determination of the first customer to be visited in the route, called rotation. The assignment choices, making the richness of the problem, are thus no more addressed in the solution structure, but implicitly determined during each move evaluation. Two meta-heuristics relying on these concepts, an iterated local search and a hybrid genetic algorithm, are presented. Extensive computational experiments demonstrate the remarkable performance of these methods on classic benchmark instances for multi-depot vehicle routing problems with and without fleet mix, as well as the notable contribution of the implicit depot choice and positioning methods to the search performance. New state-of-the-art results are obtained for multi-depot vehicle routing problems (MDVRP), and multi-depot vehicle fleet mix problems (MDVFMP) with unconstrained fleet size. The proposed concepts are fairly general, and widely applicable to many other vehicle routing variants.}, author = {Vidal, T. and Crainic, T.G. and Gendreau, M. and Prins, C.}, doi = {10.1016/j.ejor.2013.12.044}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal et al/Vidal et al. - 2014 - Implicit depot assignments and rotations in vehicle routing heuristics.pdf:pdf}, journal = {European Journal of Operational Research}, number = {1}, pages = {15--28}, title = {{Implicit depot assignments and rotations in vehicle routing heuristics}}, url = {https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2012-60.pdf}, volume = {237}, year = {2014} }

Vehicle routing variants with multiple depots and mixed fleet present intricate combinatorial aspects related to sequencing choices, vehicle type choices, depot choices, and depots positioning. This paper introduces a dynamic programming methodology for efficiently evaluating compound neighborhoods combining sequence-based moves with an optimal choice of vehicle and depot, and an optimal determination of the first customer to be visited in the route, called rotation. The assignment choices, making the richness of the problem, are thus no more addressed in the solution structure, but implicitly determined during each move evaluation. Two meta-heuristics relying on these concepts, an iterated local search and a hybrid genetic algorithm, are presented. Extensive computational experiments demonstrate the remarkable performance of these methods on classic benchmark instances for multi-depot vehicle routing problems with and without fleet mix, as well as the notable contribution of the implicit depot choice and positioning methods to the search performance. New state-of-the-art results are obtained for multi-depot vehicle routing problems (MDVRP), and multi-depot vehicle fleet mix problems (MDVFMP) with unconstrained fleet size. The proposed concepts are fairly general, and widely applicable to many other vehicle routing variants.

A unified solution framework for multi-attribute vehicle routing problems.
Vidal, T.; Crainic, T.; Gendreau, M.; and Prins, C.

Paper doi bibtex abstract 46 downloads

*European Journal of Operational Research*, 234(3): 658–673. 2014.Paper doi bibtex abstract 46 downloads

@article{Vidal2012b, abstract = {Vehicle routing attributes are extra characteristics and decisions that complement the academic problem formulations and aim to properly account for real-life application needs. Hundreds of methods have been introduced in recent years for specific attributes, but the development of a single, general-purpose algorithm, which is both efficient and applicable to a wide family of variants remains a considerable challenge. Yet, such a development is critical for understanding the proper impact of attributes on resolution approaches, and to answer the needs of actual applications. This paper contributes towards addressing these challenges with a component-based design for heuristics, targeting multi-attribute vehicle routing problems, and an efficient general-purpose solver. The proposed Unified Hybrid Genetic Search metaheuristic relies on problem-independent unified local search, genetic operators, and advanced diversity management methods. Problem specifics are confined to a limited part of the method and are addressed by means of assignment, sequencing, and route-evaluation components, which are automatically selected and adapted and provide the fundamental operators to manage attribute specificities. Extensive computational experiments on 29 prominent vehicle routing variants, 42 benchmark instance sets and overall 1099 instances, demonstrate the remarkable performance of the method which matches or outperforms the current state-of-the-art problem-tailored algorithms. Thus, generality does not necessarily go against efficiency for these problem classes.}, author = {Vidal, T. and Crainic, T.G. and Gendreau, M. and Prins, C.}, doi = {10.1016/j.ejor.2013.09.045}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal et al/Vidal et al. - 2014 - A unified solution framework for multi-attribute vehicle routing problems.pdf:pdf}, journal = {European Journal of Operational Research}, mendeley-groups = {Metaheuristics/Decompositions}, number = {3}, pages = {658--673}, title = {{A unified solution framework for multi-attribute vehicle routing problems}}, url = {https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2013-22.pdf}, volume = {234}, year = {2014} }

Vehicle routing attributes are extra characteristics and decisions that complement the academic problem formulations and aim to properly account for real-life application needs. Hundreds of methods have been introduced in recent years for specific attributes, but the development of a single, general-purpose algorithm, which is both efficient and applicable to a wide family of variants remains a considerable challenge. Yet, such a development is critical for understanding the proper impact of attributes on resolution approaches, and to answer the needs of actual applications. This paper contributes towards addressing these challenges with a component-based design for heuristics, targeting multi-attribute vehicle routing problems, and an efficient general-purpose solver. The proposed Unified Hybrid Genetic Search metaheuristic relies on problem-independent unified local search, genetic operators, and advanced diversity management methods. Problem specifics are confined to a limited part of the method and are addressed by means of assignment, sequencing, and route-evaluation components, which are automatically selected and adapted and provide the fundamental operators to manage attribute specificities. Extensive computational experiments on 29 prominent vehicle routing variants, 42 benchmark instance sets and overall 1099 instances, demonstrate the remarkable performance of the method which matches or outperforms the current state-of-the-art problem-tailored algorithms. Thus, generality does not necessarily go against efficiency for these problem classes.

2013
(4)

An iterated local search heuristic for multi-capacity bin packing and machine reassignment problems.
Masson, R.; Vidal, T.; Michallet, J.; Penna, P.; Petrucci, V.; Subramanian, A.; and Dubedout, H.

Paper doi bibtex abstract 2 downloads

*Expert Systems with Applications*, 40(13): 5266–5275. 2013.Paper doi bibtex abstract 2 downloads

@article{Masson2012a, abstract = {This paper proposes an efficient Multi-Start Iterated Local Search for Packing Problems (MS-ILS-PPs) metaheuristic for Multi-Capacity Bin Packing Problems (MCBPP) and Machine Reassignment Problems (MRP). The MCBPP is a generalization of the classical bin-packing problem in which the machine (bin) capacity and task (item) sizes are given by multiple (resource) dimensions. The MRP is a challenging and novel optimization problem, aimed at maximizing the usage of available machines by reallocating tasks/processes among those machines in a cost-efficient manner, while fulfilling several capacity, conflict, and dependency-related constraints. The proposed MS-ILS-PP approach relies on simple neighborhoods as well as problem-tailored shaking procedures. We perform computational experiments on MRP benchmark instances containing between 100 and 50,000 processes. Near-optimum multi-resource allocation and scheduling solutions are obtained while meeting specified processing-time requirements (on the order of minutes). In particular, for 9/28 instances with more than 1000 processes, the gap between the solution value and a lower bound measure is smaller than 0.1{\%}. Our optimization method is also applied to solve classical benchmark instances for the MCBPP, yielding the best known solutions and optimum ones in most cases. In addition, several upper bounds for non-solved problems were improved.}, author = {Masson, R. and Vidal, T. and Michallet, J. and Penna, P.H.V. and Petrucci, V. and Subramanian, A. and Dubedout, H.}, doi = {10.1016/j.eswa.2013.03.037}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Masson et al/Masson et al. - 2013 - An iterated local search heuristic for multi-capacity bin packing and machine reassignment problems.pdf:pdf}, journal = {Expert Systems with Applications}, number = {13}, pages = {5266--5275}, title = {{An iterated local search heuristic for multi-capacity bin packing and machine reassignment problems}}, url = {https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2012-70.pdf}, volume = {40}, year = {2013} }

This paper proposes an efficient Multi-Start Iterated Local Search for Packing Problems (MS-ILS-PPs) metaheuristic for Multi-Capacity Bin Packing Problems (MCBPP) and Machine Reassignment Problems (MRP). The MCBPP is a generalization of the classical bin-packing problem in which the machine (bin) capacity and task (item) sizes are given by multiple (resource) dimensions. The MRP is a challenging and novel optimization problem, aimed at maximizing the usage of available machines by reallocating tasks/processes among those machines in a cost-efficient manner, while fulfilling several capacity, conflict, and dependency-related constraints. The proposed MS-ILS-PP approach relies on simple neighborhoods as well as problem-tailored shaking procedures. We perform computational experiments on MRP benchmark instances containing between 100 and 50,000 processes. Near-optimum multi-resource allocation and scheduling solutions are obtained while meeting specified processing-time requirements (on the order of minutes). In particular, for 9/28 instances with more than 1000 processes, the gap between the solution value and a lower bound measure is smaller than 0.1%. Our optimization method is also applied to solve classical benchmark instances for the MCBPP, yielding the best known solutions and optimum ones in most cases. In addition, several upper bounds for non-solved problems were improved.

General solution approaches for multi-attribute vehicle routing and scheduling problems.
Vidal, T.

Paper doi bibtex 9 downloads

*4OR*, 12(1): 97–98. 2013.Paper doi bibtex 9 downloads

@article{Vidal2013, author = {Vidal, T.}, doi = {10.1007/s10288-013-0240-5}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal/Vidal - 2013 - General solution approaches for multi-attribute vehicle routing and scheduling problems.pdf:pdf}, journal = {4OR}, number = {1}, pages = {97--98}, title = {{General solution approaches for multi-attribute vehicle routing and scheduling problems}}, url = {https://link.springer.com/article/10.1007{\%}2Fs10288-013-0240-5}, volume = {12}, year = {2013} }

A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows.
Vidal, T.; Crainic, T.; Gendreau, M.; and Prins, C.

Paper doi bibtex abstract 36 downloads

*Computers & Operations Research*, 40(1): 475–489. 2013.Paper doi bibtex abstract 36 downloads

@article{Vidal2012c, abstract = {The paper presents an efficient Hybrid Genetic Search with Advanced Diversity Control for a large class of time-constrained vehicle routing problems, introducing several new features to manage the temporal dimension. New move evaluation techniques are proposed, accounting for penalized infeasible solutions with respect to time-window and duration constraints, and allowing to evaluate moves from any classical neighbourhood based on arc or node exchanges in amortized constant time. Furthermore, geometric and structural problem decompositions are developed to address efficiently large problems. The proposed algorithm outperforms all current state-of-the-art approaches on classical literature benchmark instances for any combination of periodic, multi-depot, site-dependent, and duration-constrained vehicle routing problem with time windows.}, author = {Vidal, T. and Crainic, T.G. and Gendreau, M. and Prins, C.}, doi = {10.1016/j.cor.2012.07.018}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal et al/Vidal et al. - 2013 - A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with t.pdf:pdf}, journal = {Computers {\&} Operations Research}, keywords = {Decomposition,Diversity management,Hybrid genetic algorithm,Neighbourhood search,Time windows,vehicle routing problems}, mendeley-groups = {Metaheuristics/Decompositions}, number = {1}, pages = {475--489}, title = {{A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows}}, url = {https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2011-61.pdf}, volume = {40}, year = {2013} }

The paper presents an efficient Hybrid Genetic Search with Advanced Diversity Control for a large class of time-constrained vehicle routing problems, introducing several new features to manage the temporal dimension. New move evaluation techniques are proposed, accounting for penalized infeasible solutions with respect to time-window and duration constraints, and allowing to evaluate moves from any classical neighbourhood based on arc or node exchanges in amortized constant time. Furthermore, geometric and structural problem decompositions are developed to address efficiently large problems. The proposed algorithm outperforms all current state-of-the-art approaches on classical literature benchmark instances for any combination of periodic, multi-depot, site-dependent, and duration-constrained vehicle routing problem with time windows.

Heuristics for multi-attribute vehicle routing problems: A survey and synthesis.
Vidal, T.; Crainic, T.; Gendreau, M.; and Prins, C.

Paper doi bibtex abstract 8 downloads

*European Journal of Operational Research*, 231(1): 1–21. 2013.Paper doi bibtex abstract 8 downloads

@article{Vidal2012a, abstract = {The attributes of vehicle routing problems are additional characteristics or constraints that aim to better take into account the specificities of real applications. The variants thus formed are supported by a well-developed literature, including a large variety of heuristics. This article first reviews the main classes of attributes, providing a survey of heuristics and meta-heuristics for Multi-Attribute Vehicle Routing Problems (MAVRP). It then takes a closer look at the concepts of 64 remarkable meta-heuristics, selected objectively for their outstanding performance on 15 classic MAVRP with different attributes. This cross-analysis leads to the identification of “winning strategies” in designing effective heuristics for MAVRP. This is an important step in the development of general and efficient solution methods for dealing with the large range of vehicle routing variants.}, author = {Vidal, T. and Crainic, T.G. and Gendreau, M. and Prins, C.}, doi = {10.1016/j.ejor.2013.02.053}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal et al/Vidal et al. - 2013 - Heuristics for multi-attribute vehicle routing problems A survey and synthesis.pdf:pdf}, journal = {European Journal of Operational Research}, mendeley-groups = {VRP/Surveys}, number = {1}, pages = {1--21}, title = {{Heuristics for multi-attribute vehicle routing problems: A survey and synthesis}}, url = {https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2012-05.pdf}, volume = {231}, year = {2013} }

The attributes of vehicle routing problems are additional characteristics or constraints that aim to better take into account the specificities of real applications. The variants thus formed are supported by a well-developed literature, including a large variety of heuristics. This article first reviews the main classes of attributes, providing a survey of heuristics and meta-heuristics for Multi-Attribute Vehicle Routing Problems (MAVRP). It then takes a closer look at the concepts of 64 remarkable meta-heuristics, selected objectively for their outstanding performance on 15 classic MAVRP with different attributes. This cross-analysis leads to the identification of “winning strategies” in designing effective heuristics for MAVRP. This is an important step in the development of general and efficient solution methods for dealing with the large range of vehicle routing variants.

2012
(2)

A simple and effective metaheuristic for the minimum latency problem.
Silva, M.; Subramanian, A.; Vidal, T.; and Ochi, L.

Paper doi bibtex abstract 2 downloads

*European Journal of Operational Research*, 221(3): 513–520. 2012.Paper doi bibtex abstract 2 downloads

@article{Silva2012, abstract = {The Minimum Latency Problem (MLP) is a variant of the Traveling Salesman Problem which aims to minimize the sum of arrival times at vertices. The problem arises in a number of practical applications such as logistics for relief supply, scheduling and data retrieval in computer networks. This paper introduces a simple metaheuristic for the MLP, based on a greedy randomized approach for solution construction and iterated variable neighborhood descent with random neighborhood ordering for solution improvement. Extensive computational experiments on nine sets of benchmark instances involving up to 1000 customers demonstrate the good performance of the method, which yields solutions of higher quality in less computational time when compared to the current best approaches from the literature. Optimal solutions, known for problems with up to 50 customers, are also systematically obtained in a fraction of seconds.}, author = {Silva, M.M. and Subramanian, A. and Vidal, T. and Ochi, L.S.}, doi = {10.1016/j.ejor.2012.03.044}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Silva et al/Silva et al. - 2012 - A simple and effective metaheuristic for the minimum latency problem.pdf:pdf}, journal = {European Journal of Operational Research}, mendeley-groups = {VRP-Var3-EVAL/Var3-EVAL-Cumulative}, number = {3}, pages = {513--520}, publisher = {Elsevier B.V.}, title = {{A simple and effective metaheuristic for the minimum latency problem}}, url = {http://www2.ic.uff.br/{~}satoru/conteudo/artigos/EJOR2012-Marcos.pdf}, volume = {221}, year = {2012} }

The Minimum Latency Problem (MLP) is a variant of the Traveling Salesman Problem which aims to minimize the sum of arrival times at vertices. The problem arises in a number of practical applications such as logistics for relief supply, scheduling and data retrieval in computer networks. This paper introduces a simple metaheuristic for the MLP, based on a greedy randomized approach for solution construction and iterated variable neighborhood descent with random neighborhood ordering for solution improvement. Extensive computational experiments on nine sets of benchmark instances involving up to 1000 customers demonstrate the good performance of the method, which yields solutions of higher quality in less computational time when compared to the current best approaches from the literature. Optimal solutions, known for problems with up to 50 customers, are also systematically obtained in a fraction of seconds.

A hybrid genetic algorithm for multidepot and periodic vehicle routing problems.
Vidal, T.; Crainic, T.; Gendreau, M.; Lahrichi, N.; and Rei, W.

Paper doi bibtex abstract 31 downloads

*Operations Research*, 60(3): 611–624. 2012.Paper doi bibtex abstract 31 downloads

@article{Vidal2012, abstract = {We propose an algorithmic framework that successfully addresses three vehicle routing problems: the multi-depot VRP, the periodic VRP, and the multi-depot periodic VRP with heterogeneous capacitated vehicles and constrained route duration. The meta-heuristic combines the exploration breadth of population-based evolutionary search, the aggressive-improvement capabilities of neighborhood-based meta-heuristics, and advanced population-diversity management schemes. Extensive computational experiments show that, the method performs impressively, in terms of both solution quality and computational efficiency. It particular, it either identifies the best known solutions, including the optimal ones, or identifies new best solutions for all currently available benchmark instances for the three problem classes.}, author = {Vidal, T. and Crainic, T.G. and Gendreau, M. and Lahrichi, N. and Rei, W.}, doi = {10.1287/opre.1120.1048}, file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal et al/Vidal et al. - 2012 - A hybrid genetic algorithm for multidepot and periodic vehicle routing problems.pdf:pdf}, institution = {CIRRELT}, journal = {Operations Research}, keywords = {Multi-depot multi-period vehicle routing problems,adaptive population diversity management.,hybrid populations-based meta-heuristics}, mendeley-groups = {VRP-Var1-ASSIGN/Var1-ASSIGN-PVRP}, mendeley-tags = {Multi-depot multi-period vehicle routing problems,adaptive population diversity management.,hybrid populations-based meta-heuristics}, number = {3}, pages = {611--624}, title = {{A hybrid genetic algorithm for multidepot and periodic vehicle routing problems}}, url = {https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2011-05.pdf}, volume = {60}, year = {2012} }

We propose an algorithmic framework that successfully addresses three vehicle routing problems: the multi-depot VRP, the periodic VRP, and the multi-depot periodic VRP with heterogeneous capacitated vehicles and constrained route duration. The meta-heuristic combines the exploration breadth of population-based evolutionary search, the aggressive-improvement capabilities of neighborhood-based meta-heuristics, and advanced population-diversity management schemes. Extensive computational experiments show that, the method performs impressively, in terms of both solution quality and computational efficiency. It particular, it either identifies the best known solutions, including the optimal ones, or identifies new best solutions for all currently available benchmark instances for the three problem classes.

# Embedding in another Page

Copy&paste any of the following snippets into an existing page to embed this page. For more details see the documention.

**JavaScript**(Easiest)

```
<script src="https://bibbase.org/show?bib=https%3A%2F%2Fw1.cirrelt.ca%2F%7Evidalt%2Fresources%2FMy%2520Collection.bib&jsonp=1"></script>
```

**PHP**

```
<?php
$contents = file_get_contents("https://bibbase.org/show?bib=https%3A%2F%2Fw1.cirrelt.ca%2F%7Evidalt%2Fresources%2FMy%2520Collection.bib");
print_r($contents);
?>
```

**iFrame**

```
<iframe src="https://bibbase.org/show?bib=https%3A%2F%2Fw1.cirrelt.ca%2F%7Evidalt%2Fresources%2FMy%2520Collection.bib"></iframe>
```