@inproceedings{Santana2023,
abstract = {Extensive research has been conducted, over recent years, on various ways of enhancing heuristic search for combinatorial optimization problems with machine learning algorithms. In this study, we investigate the use of predictions from graph neural networks (GNNs) in the form of heatmaps to improve the Hybrid Genetic Search (HGS), a state-of-the-art algorithm for the Capacitated Vehicle Routing Problem (CVRP). The crossover and local-search components of HGS are instrumental in finding improved solutions, yet these components essentially rely on simple greedy or random choices. It seems intuitive to attempt to incorporate additional knowledge at these levels. Throughout a vast experimental campaign on more than 10,000 problem instances, we show that exploiting more sophisticated strategies using measures of node relatedness (heatmaps, or simply distance) within these algorithmic components can significantly enhance performance. However, contrary to initial expectations, we also observed that heatmaps did not present significant advantages over simpler distance measures for these purposes. Therefore, we faced a common -- though rarely documented -- situation of overkill: GNNs can indeed improve performance on an important optimization task, but an ablation analysis demonstrated that simpler alternatives perform equally well.},
archivePrefix = {arXiv},
arxivId = {2210.12075},
author = {Santana, {\'{I}}. and Lodi, A. and Vidal, T.},
booktitle = {To appear in CPAIOR 2023},
eprint = {2210.12075},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Santana, Lodi, Vidal/Santana, Lodi, Vidal - 2023 - Neural networks for local search and crossover in vehicle routing A possible overkill.pdf:pdf},
organization = {arXiv:2210.12075},
title = {{Neural networks for local search and crossover in vehicle routing: A possible overkill?}},
url = {https://arxiv.org/pdf/2210.12075.pdf},
year = {2023}
}

Extensive research has been conducted, over recent years, on various ways of enhancing heuristic search for combinatorial optimization problems with machine learning algorithms. In this study, we investigate the use of predictions from graph neural networks (GNNs) in the form of heatmaps to improve the Hybrid Genetic Search (HGS), a state-of-the-art algorithm for the Capacitated Vehicle Routing Problem (CVRP). The crossover and local-search components of HGS are instrumental in finding improved solutions, yet these components essentially rely on simple greedy or random choices. It seems intuitive to attempt to incorporate additional knowledge at these levels. Throughout a vast experimental campaign on more than 10,000 problem instances, we show that exploiting more sophisticated strategies using measures of node relatedness (heatmaps, or simply distance) within these algorithmic components can significantly enhance performance. However, contrary to initial expectations, we also observed that heatmaps did not present significant advantages over simpler distance measures for these purposes. Therefore, we faced a common – though rarely documented – situation of overkill: GNNs can indeed improve performance on an important optimization task, but an ablation analysis demonstrated that simpler alternatives perform equally well.

@inproceedings{Florio2023a,
abstract = {Decision diagrams for classification have some notable advantages over decision trees, as their internal connections can be determined at training time and their width is not bound to grow exponentially with their depth. Accordingly, decision diagrams are usually less prone to data fragmentation in internal nodes. However, the inherent complexity of training these classifiers acted as a long-standing barrier to their widespread adoption. In this context, we study the training of optimal decision diagrams (ODDs) from a mathematical programming perspective. We introduce a novel mixed-integer linear programming model for training and demonstrate its applicability for many datasets of practical importance. Further, we show how this model can be easily extended for fairness, parsimony, and stability notions. We present numerical analyses showing that our model allows training ODDs in short computational times, and that ODDs achieve better accuracy than optimal decision trees, while allowing for improved stability without significant accuracy losses.},
archivePrefix = {arXiv},
arxivId = {2205.14500},
author = {Florio, A.M. and Martins, P. and Schiffer, M. and Serra, T. and Vidal, T.},
booktitle = {To appear in AAAI 2023},
eprint = {2205.14500},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Florio et al/Florio et al. - 2023 - Optimal decision diagrams for classification.pdf:pdf},
organization = {arXiv:2205.14500},
title = {{Optimal decision diagrams for classification}},
url = {https://arxiv.org/pdf/2205.14500.pdf},
year = {2023}
}

Decision diagrams for classification have some notable advantages over decision trees, as their internal connections can be determined at training time and their width is not bound to grow exponentially with their depth. Accordingly, decision diagrams are usually less prone to data fragmentation in internal nodes. However, the inherent complexity of training these classifiers acted as a long-standing barrier to their widespread adoption. In this context, we study the training of optimal decision diagrams (ODDs) from a mathematical programming perspective. We introduce a novel mixed-integer linear programming model for training and demonstrate its applicability for many datasets of practical importance. Further, we show how this model can be easily extended for fairness, parsimony, and stability notions. We present numerical analyses showing that our model allows training ODDs in short computational times, and that ODDs achieve better accuracy than optimal decision trees, while allowing for improved stability without significant accuracy losses.

@article{Parmentier2023,
abstract = {The rise of battery-powered vehicles has led to many new technical and method- ological hurdles. Among these, the efficient planning of an electric fleet to fulfill passenger transportation requests still represents a major challenge. This is due to the specific constraints of electric vehicles, bound by their battery autonomy and necessity of recharge planning, and the large scale of the operations, which challenges existing optimization algorithms. The purpose of this paper is to introduce a scalable column generation approach for routing and scheduling in this context. Our algorithm relies on four main ingredients: (i) a multigraph reformulation of the problem based on a characterization of non-dominated charging arcs, (ii) an efficient bi-directional pricing algorithm using tight backward bounds, (iii) sparsification approaches permitting to decrease the size of the subjacent graphs dramatically, and (iv) a diving heuristic, which locates near-optimal solutions in a fraction of the time needed for a complete branch- and-price. Through extensive computational experiments, we demonstrate that our approach significantly outperforms previous algorithms for this setting, leading to accurate solutions for problems counting several hundreds of requests.},
archivePrefix = {arXiv},
arxivId = {arXiv:2104.03823v1},
author = {Parmentier, A. and Martinelli, R. and Vidal, T.},
eprint = {arXiv:2104.03823v1},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Parmentier, Martinelli, Vidal/Parmentier, Martinelli, Vidal - 2023 - Electric vehicle fleets Scalable route and rechargescheduling through column generation(2).pdf:pdf},
institution = {arXiV:2104.03823},
journal = {Transportation Science, In Press},
title = {{Electric vehicle fleets: Scalable route and rechargescheduling through column generation}},
url = {https://arxiv.org/pdf/2104.03823.pdf},
year = {2023}
}

The rise of battery-powered vehicles has led to many new technical and method- ological hurdles. Among these, the efficient planning of an electric fleet to fulfill passenger transportation requests still represents a major challenge. This is due to the specific constraints of electric vehicles, bound by their battery autonomy and necessity of recharge planning, and the large scale of the operations, which challenges existing optimization algorithms. The purpose of this paper is to introduce a scalable column generation approach for routing and scheduling in this context. Our algorithm relies on four main ingredients: (i) a multigraph reformulation of the problem based on a characterization of non-dominated charging arcs, (ii) an efficient bi-directional pricing algorithm using tight backward bounds, (iii) sparsification approaches permitting to decrease the size of the subjacent graphs dramatically, and (iv) a diving heuristic, which locates near-optimal solutions in a fraction of the time needed for a complete branch- and-price. Through extensive computational experiments, we demonstrate that our approach significantly outperforms previous algorithms for this setting, leading to accurate solutions for problems counting several hundreds of requests.

@techreport{Sampaio2023,
abstract = {Due to their conceptual simplicity, k-means algorithm variants have been extensively used for unsupervised cluster analysis. However, one main shortcoming of these algorithms is that they essentially fit a mixture of identical spherical Gaussians to data that vastly deviates from such a distribution. In comparison, general Gaussian Mixture Models (GMMs) can fit richer structures but require estimating a quadratic number of parameters per cluster to represent the covariance matrices. This poses two main issues: (i) the underlying optimization problems are challenging due to their larger number of local minima, and (ii) their solutions can overfit the data. In this work, we design search strategies that circumvent both issues. We develop efficient global optimization algorithms for general GMMs, and we combine these algorithms with regularization strategies that avoid overfitting. Through extensive computational analyses, we observe that global optimization or regularization in isolation does not substantially improve cluster recovery. However, combining these techniques permits a completely new level of performance previously unachieved by k-means algorithm variants, unraveling vastly different cluster structures. These results shed new light on the current status quo between GMM and k-means methods and suggest the more frequent use of general GMMs for data exploration. To facilitate such applications, we provide open-source code as well as Julia packages (UnsupervisedClustering.jl and RegularizedCovarianceMatrices.jl) implementing the proposed techniques.},
archivePrefix = {arXiv},
arxivId = {2302.02450},
author = {Sampaio, R.A. and {Dias Garcia}, J. and Poggi, M. and Vidal, T.},
eprint = {2302.02450},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Sampaio et al/Sampaio et al. - 2023 - Regularization and global optimization in model-based clustering.pdf:pdf},
institution = {ArXiV: 2302.02450},
title = {{Regularization and global optimization in model-based clustering}},
url = {https://arxiv.org/pdf/2302.02450.pdf},
year = {2023}
}

Due to their conceptual simplicity, k-means algorithm variants have been extensively used for unsupervised cluster analysis. However, one main shortcoming of these algorithms is that they essentially fit a mixture of identical spherical Gaussians to data that vastly deviates from such a distribution. In comparison, general Gaussian Mixture Models (GMMs) can fit richer structures but require estimating a quadratic number of parameters per cluster to represent the covariance matrices. This poses two main issues: (i) the underlying optimization problems are challenging due to their larger number of local minima, and (ii) their solutions can overfit the data. In this work, we design search strategies that circumvent both issues. We develop efficient global optimization algorithms for general GMMs, and we combine these algorithms with regularization strategies that avoid overfitting. Through extensive computational analyses, we observe that global optimization or regularization in isolation does not substantially improve cluster recovery. However, combining these techniques permits a completely new level of performance previously unachieved by k-means algorithm variants, unraveling vastly different cluster structures. These results shed new light on the current status quo between GMM and k-means methods and suggest the more frequent use of general GMMs for data exploration. To facilitate such applications, we provide open-source code as well as Julia packages (UnsupervisedClustering.jl and RegularizedCovarianceMatrices.jl) implementing the proposed techniques.

@techreport{Forel2023,
abstract = {Data-driven optimization uses contextual information and machine learning algorithms to find solutions to decision problems with uncertain parameters. While a vast body of work is dedicated to interpreting machine learning models in the classification setting, explaining decision pipelines involving learning algorithms remains unaddressed. This lack of interpretability can block the adoption of data-driven solutions as practitioners may not understand or trust the recommended decisions. We bridge this gap by introducing a counterfactual explanation methodology tailored to explain solutions to data-driven problems. We introduce two classes of explanations and develop methods to find nearest explanations of random forest and nearest-neighbor predictors. We demonstrate our approach by explaining key problems in operations management such as inventory management and routing.},
archivePrefix = {arXiv},
arxivId = {2301.10074},
author = {Forel, A. and Parmentier, A. and Vidal, T.},
eprint = {2301.10074},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Forel, Parmentier, Vidal/Forel, Parmentier, Vidal - 2023 - Explainable data-driven optimization From context to decision and back again.pdf:pdf},
institution = {ArXiV: 2301.10074},
title = {{Explainable data-driven optimization: From context to decision and back again}},
url = {https://arxiv.org/pdf/2301.10074.pdf},
year = {2023}
}

Data-driven optimization uses contextual information and machine learning algorithms to find solutions to decision problems with uncertain parameters. While a vast body of work is dedicated to interpreting machine learning models in the classification setting, explaining decision pipelines involving learning algorithms remains unaddressed. This lack of interpretability can block the adoption of data-driven solutions as practitioners may not understand or trust the recommended decisions. We bridge this gap by introducing a counterfactual explanation methodology tailored to explain solutions to data-driven problems. We introduce two classes of explanations and develop methods to find nearest explanations of random forest and nearest-neighbor predictors. We demonstrate our approach by explaining key problems in operations management such as inventory management and routing.

@article{Florio2023,
author = {Florio, A.M. and Gendreau, M. and Hartl, R.F. and Minner, S. and Vidal, T.},
doi = {10.1016/j.ejor.2022.10.045},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Florio et al/Florio et al. - 2023 - Recent advances in vehicle routing with stochastic demands Bayesian learning for correlated demands and elemen(2).pdf:pdf},
issn = {0377-2217},
journal = {European Journal of Operational Research},
pages = {1081----1093},
title = {{Recent advances in vehicle routing with stochastic demands: Bayesian learning for correlated demands and elementary branch-price-and-cut}},
url = {https://doi.org/10.1016/j.ejor.2022.10.045},
volume = {306},
year = {2023}
}

@techreport{Ferreira2022,
abstract = {Influence propagation has been the subject of extensive study due to its important role in social networks, epidemiology, and many other areas. Understanding propagation mechanisms is critical to control the spread of fake news or epidemics. In this work, we study the problem of detecting the smallest group of users whose conversion achieves, through propagation, a certain influence level over the network, therefore giving valuable information on the propagation behavior in this network. We develop mixed integer programming algorithms to solve this problem. The core of our algorithm is based on new valid inequalities, cutting planes, and separation algorithms embedded into a branch-and-cut algorithm. We additionally introduce a compact formulation relying on fewer variables. Through extensive computational experiments, we observe that the proposed methods can optimally solve many previously-open benchmark instances, and otherwise achieve small optimality gaps. These experiments also provide various insights into the benefits of different mathematical formulations.},
archivePrefix = {arXiv},
arxivId = {2209.13065},
author = {Ferreira, V. and Pessoa, A. and Vidal, T.},
eprint = {2209.13065},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Ferreira, Pessoa, Vidal/Ferreira, Pessoa, Vidal - 2022 - Influence optimization in networks New formulations and valid inequalities.pdf:pdf},
institution = {arXiv:2209.13065},
keywords = {branch-and-cut,influence optimization,integer programming,valid inequalities},
title = {{Influence optimization in networks: New formulations and valid inequalities}},
url = {https://arxiv.org/pdf/2209.13065.pdf},
year = {2022}
}

Influence propagation has been the subject of extensive study due to its important role in social networks, epidemiology, and many other areas. Understanding propagation mechanisms is critical to control the spread of fake news or epidemics. In this work, we study the problem of detecting the smallest group of users whose conversion achieves, through propagation, a certain influence level over the network, therefore giving valuable information on the propagation behavior in this network. We develop mixed integer programming algorithms to solve this problem. The core of our algorithm is based on new valid inequalities, cutting planes, and separation algorithms embedded into a branch-and-cut algorithm. We additionally introduce a compact formulation relying on fewer variables. Through extensive computational experiments, we observe that the proposed methods can optimally solve many previously-open benchmark instances, and otherwise achieve small optimality gaps. These experiments also provide various insights into the benefits of different mathematical formulations.

@techreport{Serrano2022,
abstract = {We study the feature-based newsvendor problem, in which a decision-maker has access to historical data consisting of demand observations and exogenous features. In this setting, we investigate feature selection, aiming to derive sparse, explainable models with improved out-of-sample performance. Up to now, state-of-the-art methods utilize regularization, which penalizes the number of selected features or the norm of the solution vector. As an alternative, we introduce a novel bilevel programming formulation. The upper-level problem selects a subset of features that minimizes an estimate of the out-of-sample cost of ordering decisions based on a held-out validation set. The lower-level problem learns the optimal coefficients of the decision function on a training set, using only the features selected by the upper-level. We present a mixed integer linear program reformulation for the bilevel program, which can be solved to optimality with standard optimization solvers. Our computational experiments show that the method accurately recovers ground-truth features already for instances with a sample size of a few hundred observations. In contrast, regularization-based techniques often fail at feature recovery or require thousands of observations to obtain similar accuracy. Regarding out-of-sample generalization, we achieve improved or comparable cost performance.},
archivePrefix = {arXiv},
arxivId = {2209.05093},
author = {Serrano, B. and Minner, S. and Schiffer, M. and Vidal, T.},
eprint = {2209.05093},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Serrano et al/Serrano et al. - 2022 - Bilevel optimization for feature selection in the data-driven newsvendor problem.pdf:pdf},
institution = {arXiv:2209.05093},
title = {{Bilevel optimization for feature selection in the data-driven newsvendor problem}},
url = {https://arxiv.org/pdf/2209.05093.pdf},
year = {2022}
}

We study the feature-based newsvendor problem, in which a decision-maker has access to historical data consisting of demand observations and exogenous features. In this setting, we investigate feature selection, aiming to derive sparse, explainable models with improved out-of-sample performance. Up to now, state-of-the-art methods utilize regularization, which penalizes the number of selected features or the norm of the solution vector. As an alternative, we introduce a novel bilevel programming formulation. The upper-level problem selects a subset of features that minimizes an estimate of the out-of-sample cost of ordering decisions based on a held-out validation set. The lower-level problem learns the optimal coefficients of the decision function on a training set, using only the features selected by the upper-level. We present a mixed integer linear program reformulation for the bilevel program, which can be solved to optimality with standard optimization solvers. Our computational experiments show that the method accurately recovers ground-truth features already for instances with a sample size of a few hundred observations. In contrast, regularization-based techniques often fail at feature recovery or require thousands of observations to obtain similar accuracy. Regarding out-of-sample generalization, we achieve improved or comparable cost performance.

@techreport{Bouvier2022,
abstract = {This paper is the fruit of a partnership with Renault. Their backward logistic requires to solve a continent-scale multi-attribute inventory routing problem (IRP). With an average of {\$}30{\$} commodities, {\$}16{\$} depots, and {\$}600{\$} customers spread across a continent, our instances are orders of magnitude larger than those in the literature. Existing algorithms do not scale. We propose a large neighborhood search (LNS). To make it work, (1) we generalize existing split delivery vehicle routing problem and IRP neighborhoods to this context, (2) we turn a state-of-the art matheuristic for medium-scale IRP into a large neighborhood, and (3) we introduce two novel perturbations: the reinsertion of a customer and that of a commodity into the IRP solution. We also derive a new lower bound based on a flow relaxation. In order to stimulate the research on large-scale IRP, we introduce a library of industrial instances. We benchmark our algorithms on these instances and make our code open-source. Extensive numerical experiments highlight the relevance of each component of our LNS.},
archivePrefix = {arXiv},
arxivId = {2209.00412},
author = {Bouvier, L. and Dalle, G. and Parmentier, A. and Vidal, T.},
eprint = {2209.00412},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Bouvier et al/Bouvier et al. - 2022 - Solving a continent-scale inventory routing problem at Renault.pdf:pdf},
institution = {arXiv:2209.00412},
title = {{Solving a continent-scale inventory routing problem at Renault}},
url = {https://arxiv.org/pdf/2209.00412.pdf},
year = {2022}
}

This paper is the fruit of a partnership with Renault. Their backward logistic requires to solve a continent-scale multi-attribute inventory routing problem (IRP). With an average of $}30{$ commodities, $}16{$ depots, and $}600{$ customers spread across a continent, our instances are orders of magnitude larger than those in the literature. Existing algorithms do not scale. We propose a large neighborhood search (LNS). To make it work, (1) we generalize existing split delivery vehicle routing problem and IRP neighborhoods to this context, (2) we turn a state-of-the art matheuristic for medium-scale IRP into a large neighborhood, and (3) we introduce two novel perturbations: the reinsertion of a customer and that of a commodity into the IRP solution. We also derive a new lower bound based on a flow relaxation. In order to stimulate the research on large-scale IRP, we introduce a library of industrial instances. We benchmark our algorithms on these instances and make our code open-source. Extensive numerical experiments highlight the relevance of each component of our LNS.

@techreport{Santana2022,
abstract = {The classical hinge-loss support vector machines (SVMs) model is sensitive to outlier observations due to the unboundedness of its loss function. To circumvent this issue, recent studies have focused on non-convex loss functions, such as the hard-margin loss, which associates a constant penalty to any misclassified or within-margin sample. Applying this loss function yields much-needed robustness for critical applications but it also leads to an NP-hard model that makes training difficult, since current exact optimization algorithms show limited scalability, whereas heuristics are not able to find high-quality solutions consistently. Against this background, we propose new integer programming strategies that significantly improve our ability to train the hard-margin SVM model to global optimality. We introduce an iterative sampling and decomposition approach, in which smaller subproblems are used to separate combinatorial Benders' cuts. Those cuts, used within a branch-and-cut algorithm, permit to converge much more quickly towards a global optimum. Through extensive numerical analyses on classical benchmark data sets, our solution algorithm solves, for the first time, 117 new data sets to optimality and achieves a reduction of 50{\%} in the average optimality gap for the hardest datasets of the benchmark.},
archivePrefix = {arXiv},
arxivId = {2207.07690},
author = {Santana, {\'{I}}. and Serrano, B. and Schiffer, M. and Vidal, T.},
eprint = {2207.07690},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Santana et al/Santana et al. - 2022 - Support vector machines with the hard-margin loss Optimal training via combinatorial Benders' cuts.pdf:pdf},
institution = {arXiv:2207.07690},
title = {{Support vector machines with the hard-margin loss: Optimal training via combinatorial Benders' cuts}},
url = {https://arxiv.org/pdf/2207.07690.pdf},
year = {2022}
}

The classical hinge-loss support vector machines (SVMs) model is sensitive to outlier observations due to the unboundedness of its loss function. To circumvent this issue, recent studies have focused on non-convex loss functions, such as the hard-margin loss, which associates a constant penalty to any misclassified or within-margin sample. Applying this loss function yields much-needed robustness for critical applications but it also leads to an NP-hard model that makes training difficult, since current exact optimization algorithms show limited scalability, whereas heuristics are not able to find high-quality solutions consistently. Against this background, we propose new integer programming strategies that significantly improve our ability to train the hard-margin SVM model to global optimality. We introduce an iterative sampling and decomposition approach, in which smaller subproblems are used to separate combinatorial Benders' cuts. Those cuts, used within a branch-and-cut algorithm, permit to converge much more quickly towards a global optimum. Through extensive numerical analyses on classical benchmark data sets, our solution algorithm solves, for the first time, 117 new data sets to optimality and achieves a reduction of 50% in the average optimality gap for the hardest datasets of the benchmark.

@techreport{Nekooghadirli2022,
abstract = {An equitable distribution of workload is essential when deploying vehicle routing solutions in practice. For this reason, previous studies have formulated vehicle routing problems with workload-balance objectives or constraints, leading to trade-off solutions between routing costs and workload equity. These methods consider a single planning period; however, equity is often sought over several days in practice. In this work, we show that workload equity over multiple periods can be achieved without impact on transportation costs when the planning horizon is sufficiently large. To achieve this, we design a two-phase method to solve multi-period vehicle routing problems with workload balance. Firstly, our approach produces solutions with minimal distance for each period. Next, the resulting routes are allocated to drivers to obtain equitable workloads over the planning horizon. We conduct extensive numerical experiments to measure the performance of the proposed approach and the level of workload equity achieved for different planning-horizon lengths. For horizons of five days or more, we observe that near-optimal workload equity and optimal routing costs are jointly achievable.},
archivePrefix = {arXiv},
arxivId = {2206.14596},
author = {Nekooghadirli, N. and Gendreau, M. and Potvin, J.-Y. and Vidal, T.},
eprint = {2206.14596},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Nekooghadirli et al/Nekooghadirli et al. - 2022 - Workload equity in multi-period vehicle routing problems.pdf:pdf},
institution = {arXiv:2206.14596},
title = {{Workload equity in multi-period vehicle routing problems}},
url = {https://arxiv.org/pdf/2206.14596.pdf},
year = {2022}
}

An equitable distribution of workload is essential when deploying vehicle routing solutions in practice. For this reason, previous studies have formulated vehicle routing problems with workload-balance objectives or constraints, leading to trade-off solutions between routing costs and workload equity. These methods consider a single planning period; however, equity is often sought over several days in practice. In this work, we show that workload equity over multiple periods can be achieved without impact on transportation costs when the planning horizon is sufficiently large. To achieve this, we design a two-phase method to solve multi-period vehicle routing problems with workload balance. Firstly, our approach produces solutions with minimal distance for each period. Next, the resulting routes are allocated to drivers to obtain equitable workloads over the planning horizon. We conduct extensive numerical experiments to measure the performance of the proposed approach and the level of workload equity achieved for different planning-horizon lengths. For horizons of five days or more, we observe that near-optimal workload equity and optimal routing costs are jointly achievable.

@article{Florio2022,
abstract = {We consider the vehicle routing problem with stochastic demands (VRPSD), a problem in which customer demands are known in distribution at the route planning stage and revealed during route execution upon arrival at each customer. A long-standing open question in the VRPSD concerns the benefits of allowing, during route execution, partial reordering of the planned customer visits. Given the practical importance of this question and the growing interest on the VRPSD under optimal restocking, we study the VRPSD under a recourse policy known as the switch policy. The switch policy is a canoni- cal reoptimization policy that permits only pairs of successive customers to be reordered. We consider this policy jointly with optimal preventive restocking and introduce a branch-cut-and-price algorithm to compute optimal a priori routing plans in this context. At its core, this algorithm features pricing routines where value functions represent the expected cost-to-go along planned routes for all possible states and reordering decisions. To ensure pricing tractability, we adopt a strategy that combines elementary pricing with completion bounds of varying complexity, andwe solve the pricing problemwithout rely- ing on dominance rules. Our numerical experiments demonstrate the effectiveness of the algorithm for solving instances with up to 50 customers. Notably, they also give us new insights into the value of reoptimization. The switch policy enables significant cost savings over optimal restocking when the planned routes come from an algorithm built on a deterministic approximation of the data, an important scenario given the difficulty of find- ing optimal VRPSD solutions. The benefits are smaller when comparing optimal a priori VRPSD solutions obtained for both recourse policies. As it appears, further cost savings may require joint reordering and reassignment of customer visits among vehicles when the context permits.},
author = {Florio, A.M. and Feillet, D. and Poggi, M. and Vidal, T.},
doi = {trsc.2022.1129},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Florio et al/Florio et al. - 2022 - Vehicle routing with stochastic demands and partial reoptimization(2).pdf:pdf},
journal = {Transportation Science},
title = {{Vehicle routing with stochastic demands and partial reoptimization}},
url = {https://arxiv.org/pdf/2201.08866.pdf},
year = {2022}
}

We consider the vehicle routing problem with stochastic demands (VRPSD), a problem in which customer demands are known in distribution at the route planning stage and revealed during route execution upon arrival at each customer. A long-standing open question in the VRPSD concerns the benefits of allowing, during route execution, partial reordering of the planned customer visits. Given the practical importance of this question and the growing interest on the VRPSD under optimal restocking, we study the VRPSD under a recourse policy known as the switch policy. The switch policy is a canoni- cal reoptimization policy that permits only pairs of successive customers to be reordered. We consider this policy jointly with optimal preventive restocking and introduce a branch-cut-and-price algorithm to compute optimal a priori routing plans in this context. At its core, this algorithm features pricing routines where value functions represent the expected cost-to-go along planned routes for all possible states and reordering decisions. To ensure pricing tractability, we adopt a strategy that combines elementary pricing with completion bounds of varying complexity, andwe solve the pricing problemwithout rely- ing on dominance rules. Our numerical experiments demonstrate the effectiveness of the algorithm for solving instances with up to 50 customers. Notably, they also give us new insights into the value of reoptimization. The switch policy enables significant cost savings over optimal restocking when the planned routes come from an algorithm built on a deterministic approximation of the data, an important scenario given the difficulty of find- ing optimal VRPSD solutions. The benefits are smaller when comparing optimal a priori VRPSD solutions obtained for both recourse policies. As it appears, further cost savings may require joint reordering and reassignment of customer visits among vehicles when the context permits.

@article{Pacheco2022,
archivePrefix = {arXiv},
arxivId = {arXiv:2107.05189v1},
author = {Pacheco, T. and Martinelli, R. and Subramanian, A. and A.M.Toffolo, T. and Vidal, T.},
eprint = {arXiv:2107.05189v1},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Pacheco et al/Pacheco et al. - 2022 - Exponential-size neighborhoods for the pickup-and-delivery traveling salesman problem(2).pdf:pdf},
institution = {arXiv:2107.05189},
journal = {Transportation Science, Articles in Advance},
title = {{Exponential-size neighborhoods for the pickup-and-delivery traveling salesman problem}},
url = {https://arxiv.org/pdf/2107.05189.pdf},
year = {2022}
}

@article{Vidal2022,
abstract = {The vehicle routing problem is one of the most studied combinatorial optimization topics, due to its practical importance and methodological interest. Yet, despite extensive methodological progress, many recent studies are hampered by the limited access to simple and efficient open-source solution methods. Given the sophistication of current algorithms, reimplementation is becoming a difficult and time-consuming exercise that requires extensive care for details to be truly successful. Against this background, we use the opportunity of this short paper to introduce a simple – open-source – implementation of the hybrid genetic search (HGS) specialized to the capacitated vehicle routing problem (CVRP). This state-of-the-art algorithm uses the same general methodology as Vidal et al. (2012) but also includes additional methodological improvements and lessons learned over the past decade of research. In particular, it includes an additional neighborhood called SWAP* which consists in exchanging two customers between different routes without an insertion in place. As highlighted in our study, an efficient exploration of SWAP* moves significantly contributes to the performance of local searches. Moreover, as observed in experimental comparisons with other recent approaches on the classical instances of Uchoa et al. (2017), HGS still stands as a leading metaheuristic regarding solution quality, convergence speed, and conceptual simplicity.},
author = {Vidal, T.},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal/Vidal - 2022 - Hybrid genetic search for the CVRP Open-source implementation and SWAP neighborhood(2).pdf:pdf},
journal = {Computers and Operations Research},
keywords = {hybrid genetic search,neighborhood search,open,vehicle routing problem},
pages = {105643},
title = {{Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood}},
url = {https://arxiv.org/pdf/2012.10384.pdf},
volume = {140},
year = {2022}
}

The vehicle routing problem is one of the most studied combinatorial optimization topics, due to its practical importance and methodological interest. Yet, despite extensive methodological progress, many recent studies are hampered by the limited access to simple and efficient open-source solution methods. Given the sophistication of current algorithms, reimplementation is becoming a difficult and time-consuming exercise that requires extensive care for details to be truly successful. Against this background, we use the opportunity of this short paper to introduce a simple – open-source – implementation of the hybrid genetic search (HGS) specialized to the capacitated vehicle routing problem (CVRP). This state-of-the-art algorithm uses the same general methodology as Vidal et al. (2012) but also includes additional methodological improvements and lessons learned over the past decade of research. In particular, it includes an additional neighborhood called SWAP* which consists in exchanging two customers between different routes without an insertion in place. As highlighted in our study, an efficient exploration of SWAP* moves significantly contributes to the performance of local searches. Moreover, as observed in experimental comparisons with other recent approaches on the classical instances of Uchoa et al. (2017), HGS still stands as a leading metaheuristic regarding solution quality, convergence speed, and conceptual simplicity.

@techreport{Forel2022,
abstract = {Counterfactual explanations describe how to modify a feature vector in order to flip the outcome of a trained classifier. Several heuristic and optimal methods have been proposed to generate these explanations. However, the robustness of counterfactual explanations when the classifier is re-trained has yet to be studied. Our goal is to obtain counterfactual explanations for random forests that are robust to algorithmic uncertainty. We study the link between the robustness of ensemble models and the robustness of base learners and frame the generation of robust counterfactual explanations as a chance-constrained optimization problem. We develop a practical method with good empirical performance and provide finite-sample and asymptotic guarantees for simple random forests of stumps. We show that existing methods give surprisingly low robustness: the validity of naive counterfactuals is below {\$}50\backslash{\%}{\$} on most data sets and can fall to {\$}20\backslash{\%}{\$} on large problem instances with many features. Even with high plausibility, counterfactual explanations often exhibit low robustness to algorithmic uncertainty. In contrast, our method achieves high robustness with only a small increase in the distance from counterfactual explanations to their initial observations. Furthermore, we highlight the connection between the robustness of counterfactual explanations and the predictive importance of features.},
archivePrefix = {arXiv},
arxivId = {2205.14116},
author = {Forel, A. and Parmentier, A. and Vidal, T.},
eprint = {2205.14116},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Forel, Parmentier, Vidal/Forel, Parmentier, Vidal - 2022 - Don't Explain Noise Robust Counterfactuals for Randomized Ensembles(2).pdf:pdf},
institution = {arXiv:2205.14116},
title = {{Don't Explain Noise: Robust Counterfactuals for Randomized Ensembles}},
url = {http://arxiv.org/abs/2205.14116},
year = {2022}
}

Counterfactual explanations describe how to modify a feature vector in order to flip the outcome of a trained classifier. Several heuristic and optimal methods have been proposed to generate these explanations. However, the robustness of counterfactual explanations when the classifier is re-trained has yet to be studied. Our goal is to obtain counterfactual explanations for random forests that are robust to algorithmic uncertainty. We study the link between the robustness of ensemble models and the robustness of base learners and frame the generation of robust counterfactual explanations as a chance-constrained optimization problem. We develop a practical method with good empirical performance and provide finite-sample and asymptotic guarantees for simple random forests of stumps. We show that existing methods give surprisingly low robustness: the validity of naive counterfactuals is below $}50\{%}{$ on most data sets and can fall to $}20\{%}{$ on large problem instances with many features. Even with high plausibility, counterfactual explanations often exhibit low robustness to algorithmic uncertainty. In contrast, our method achieves high robustness with only a small increase in the distance from counterfactual explanations to their initial observations. Furthermore, we highlight the connection between the robustness of counterfactual explanations and the predictive importance of features.

@article{Gribel2021,
abstract = {Pairwise relational information is a useful way of providing partial supervision in domains where class labels are difficult to acquire. This work presents a clustering model that incorporates pairwise annotations in the form of must-link and cannot-link relations and considers possible annotation inaccuracies (i.e., a common setting when experts provide pairwise supervision). We propose a generative model that assumes Gaussian-distributed data samples along with must-link and cannot-link relations generated by stochastic block models. We adopt a maximum-likelihood approach and demonstrate that, even when supervision is weak and inaccurate, accounting for relational information significantly improves clustering performance. Relational information also helps to detect meaningful groups in real-world datasets that do not fit the original data-distribution assumptions. Additionally, we extend the model to integrate prior knowledge of experts' accuracy and discuss circumstances in which the use of this knowledge is beneficial.},
archivePrefix = {arXiv},
arxivId = {2104.02146},
author = {Gribel, D. and Gendreau, M. and Vidal, T.},
eprint = {2104.02146},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Gribel, Gendreau, Vidal/Gribel, Gendreau, Vidal - 2022 - Semi-supervised clustering with inaccurate pairwise annotations.pdf:pdf},
journal = {Information Sciences},
number = {C},
pages = {441--457},
title = {{Semi-supervised clustering with inaccurate pairwise annotations}},
url = {https://arxiv.org/pdf/2104.02146.pdf},
volume = {607},
year = {2022}
}

Pairwise relational information is a useful way of providing partial supervision in domains where class labels are difficult to acquire. This work presents a clustering model that incorporates pairwise annotations in the form of must-link and cannot-link relations and considers possible annotation inaccuracies (i.e., a common setting when experts provide pairwise supervision). We propose a generative model that assumes Gaussian-distributed data samples along with must-link and cannot-link relations generated by stochastic block models. We adopt a maximum-likelihood approach and demonstrate that, even when supervision is weak and inaccurate, accounting for relational information significantly improves clustering performance. Relational information also helps to detect meaningful groups in real-world datasets that do not fit the original data-distribution assumptions. Additionally, we extend the model to integrate prior knowledge of experts' accuracy and discuss circumstances in which the use of this knowledge is beneficial.

@techreport{Queiroga2021b,
abstract = {We introduce a benchmark of 10,000 instances with heterogeneous characteristics for the capacitated vehicle routing problem. We also provide optimal solutions for almost all of them along with a generator to produce additional training and validation data. This benchmark aims to permit a more systematic comparison of machine learning based search algorithms on this important problem. We also emit recommendations regarding the correct use of this dataset.},
archivePrefix = {arXiv},
arxivId = {2109.13983},
author = {Queiroga, E. and Sadykov, R. and Uchoa, E. and Vidal, T.},
eprint = {2109.13983},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Queiroga et al/Queiroga et al. - 2021 - 10,000 optimal CVRP solutions for testing machine learning based heuristics.pdf:pdf},
title = {{10,000 optimal CVRP solutions for testing machine learning based heuristics}},
url = {http://arxiv.org/abs/2109.13983},
year = {2021}
}

We introduce a benchmark of 10,000 instances with heterogeneous characteristics for the capacitated vehicle routing problem. We also provide optimal solutions for almost all of them along with a generator to produce additional training and validation data. This benchmark aims to permit a more systematic comparison of machine learning based search algorithms on this important problem. We also emit recommendations regarding the correct use of this dataset.

@techreport{Herthel2021,
abstract = {Some of today's greatest challenges in urban environments concern individual mobility and rapid parcel delivery. Given the surge of e-commerce and the ever-increasing volume of goods to be delivered, we explore possible logistic solutions by proposing algorithms to add parcel-transport services to ride-hailing systems. Toward this end, we present and solve mixed-integer linear programming (MILP) formulations of the share-a-ride problem and quantitatively analyze the service revenues and use of vehicle resources. We create five scenarios that represent joint transportation situations for parcels and people, and that consider different densities in request types and different requirements for vehicle resources. For one scenario, we propose an alternative MILP formulation that significantly reduces computation times. The proposed model also improves scalability by solving instances with 260{\%} more requests than those solved with general MILP. The results show that the greatest profit margins occur when several parcels share trips with customers. In contrast, with all metrics considered, the worst results occur when parcels and people are transported in separate dedicated vehicles. The integration of parcel services in ride-hailing systems also reduces vehicle waiting times when the number of parcel requests exceeds the number of ride-hailing customers.},
archivePrefix = {arXiv},
arxivId = {2110.15152},
author = {Herthel, AB and Hartl, R and Vidal, T and Subramanian, A},
eprint = {2110.15152},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Herthel et al/Herthel et al. - 2021 - Share-a-ride problems Models and solution algorithms.pdf:pdf},
institution = {arXiv:2110.15152},
keywords = {generalized vehicle routing,ride-hailing,share-a-ride problem,vehicle routing},
title = {{Share-a-ride problems: Models and solution algorithms}},
url = {http://arxiv.org/abs/2110.15152},
year = {2021}
}

Some of today's greatest challenges in urban environments concern individual mobility and rapid parcel delivery. Given the surge of e-commerce and the ever-increasing volume of goods to be delivered, we explore possible logistic solutions by proposing algorithms to add parcel-transport services to ride-hailing systems. Toward this end, we present and solve mixed-integer linear programming (MILP) formulations of the share-a-ride problem and quantitatively analyze the service revenues and use of vehicle resources. We create five scenarios that represent joint transportation situations for parcels and people, and that consider different densities in request types and different requirements for vehicle resources. For one scenario, we propose an alternative MILP formulation that significantly reduces computation times. The proposed model also improves scalability by solving instances with 260% more requests than those solved with general MILP. The results show that the greatest profit margins occur when several parcels share trips with customers. In contrast, with all metrics considered, the worst results occur when parcels and people are transported in separate dedicated vehicles. The integration of parcel services in ride-hailing systems also reduces vehicle waiting times when the number of parcel requests exceeds the number of ride-hailing customers.

@techreport{Santini2021,
author = {Santini, A. and Schneider, M. and Vidal, T. and Vigo, D.},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Santini et al/Santini et al. - 2021 - Decomposition strategies for vehicle routing heuristics.pdf:pdf},
institution = {Optimization Online: 8316},
pages = {1--18},
title = {{Decomposition strategies for vehicle routing heuristics}},
url = {http://www.optimization-online.org/DB{\_}FILE/2021/03/8316.pdf},
year = {2021}
}

@techreport{Serrano2021,
abstract = {The Degree-Corrected Stochastic Block Model (DCSBM) is a popular model to generate random graphs with community structure given an expected degree sequence. The standard approach of community detection based on the DCSBM is to search for the model parameters that are the most likely to have produced the observed network data through maximum likelihood estimation (MLE). Current techniques for the MLE problem are heuristics, and therefore do not guarantee convergence to the optimum. We present mathematical programming formulations and exact solution methods that can provably find the model parameters and community assignments of maximum likelihood given an observed graph. We compare these exact methods with classical heuristic algorithms based on expectation-maximization (EM). The solutions given by exact methods give us a principled way of measuring the experimental performance of classical heuristics and comparing different variations thereof.},
archivePrefix = {arXiv},
arxivId = {arXiv:2101.12336v1},
author = {Serrano, B. and Vidal, T.},
eprint = {arXiv:2101.12336v1},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Serrano, Vidal/Serrano, Vidal - 2021 - Community detection in the stochastic block model by mixed integer programming.pdf:pdf},
institution = {arXiv:2101.12336},
title = {{Community detection in the stochastic block model by mixed integer programming}},
url = {https://arxiv.org/pdf/2101.12336.pdf},
year = {2021}
}

The Degree-Corrected Stochastic Block Model (DCSBM) is a popular model to generate random graphs with community structure given an expected degree sequence. The standard approach of community detection based on the DCSBM is to search for the model parameters that are the most likely to have produced the observed network data through maximum likelihood estimation (MLE). Current techniques for the MLE problem are heuristics, and therefore do not guarantee convergence to the optimum. We present mathematical programming formulations and exact solution methods that can provably find the model parameters and community assignments of maximum likelihood given an observed graph. We compare these exact methods with classical heuristic algorithms based on expectation-maximization (EM). The solutions given by exact methods give us a principled way of measuring the experimental performance of classical heuristics and comparing different variations thereof.

@article{Vidal2021,
abstract = {Vehicle routing algorithms usually reformulate the road network into a complete graph in which each arc represents the shortest path between two locations. Studies on time-dependent routing followed this model and therefore defined the speed functions on the complete graph. We argue that this model is often inadequate, in particular for arc routing problems involving services on edges of a road network. To fill this gap, we formally define the time-dependent capacitated arc routing problem (TDCARP), with travel and service speed functions given directly at the network level. Under these assumptions, the quickest path between locations can change over time, leading to a complex problem that challenges the capabilities of current solution methods. We introduce effective algorithms for preprocessing quickest paths in a closed form, efficient data structures for travel time queries during routing optimization, as well as heuristic and exact solution approaches for the TDCARP. Our heuristic uses the hybrid genetic search principle with tailored solution-decoding algorithms and lower bounds for filtering moves. Our branch-and-price algorithm exploits dedicated pricing routines, heuristic dominance rules and completion bounds to find optimal solutions for problem counting up to 75 services. Based on these algorithms, we measure the benefits of time-dependent routing optimization for different levels of travel-speed data accuracy.},
author = {Vidal, T. and Martinelli, R. and Pham, T.A. and H{\`{a}}, M.H.},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal et al/Vidal et al. - 2021 - Arc routing with time-dependent travel times and paths(2).pdf:pdf},
journal = {Transportation Science},
number = {3},
pages = {706--724},
title = {{Arc routing with time-dependent travel times and paths}},
url = {https://arxiv.org/pdf/2004.14473.pdf},
volume = {55},
year = {2021}
}

Vehicle routing algorithms usually reformulate the road network into a complete graph in which each arc represents the shortest path between two locations. Studies on time-dependent routing followed this model and therefore defined the speed functions on the complete graph. We argue that this model is often inadequate, in particular for arc routing problems involving services on edges of a road network. To fill this gap, we formally define the time-dependent capacitated arc routing problem (TDCARP), with travel and service speed functions given directly at the network level. Under these assumptions, the quickest path between locations can change over time, leading to a complex problem that challenges the capabilities of current solution methods. We introduce effective algorithms for preprocessing quickest paths in a closed form, efficient data structures for travel time queries during routing optimization, as well as heuristic and exact solution approaches for the TDCARP. Our heuristic uses the hybrid genetic search principle with tailored solution-decoding algorithms and lower bounds for filtering moves. Our branch-and-price algorithm exploits dedicated pricing routines, heuristic dominance rules and completion bounds to find optimal solutions for problem counting up to 75 services. Based on these algorithms, we measure the benefits of time-dependent routing optimization for different levels of travel-speed data accuracy.

@article{Arnold2021,
abstract = {We introduce pattern injection local search (PILS), an optimization strategy that uses pattern mining to explore high-order local-search neighborhoods, and illustrate its application on the vehicle routing problem. PILS operates by storing a limited number of frequent patterns from elite solutions. During the local search, each pattern is used to define one move in which 1) incompatible edges are disconnected, 2) the edges defined by the pattern are reconnected, and 3) the remaining solution fragments are optimally reconnected. Each such move is accepted only in case of solution improvement. As visible in our experiments, this strategy results in a new paradigm of local search, which complements and enhances classical search approaches in a controllable amount of computational time. We demonstrate that PILS identifies useful high-order moves (e.g., 9-opt and 10-opt) which would otherwise not be found by enumeration, and that it significantly improves the performance of state-of-the-art population-based and neighborhood-centered metaheuristics.},
author = {Arnold, F. and Santana, {\'{I}}.G. and S{\"{o}}rensen, K. and Vidal, T.},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Arnold et al/Arnold et al. - 2021 - PILS Exploring high-order neighborhoods by pattern mining and injection(2).pdf:pdf},
institution = {ArXiV: 1912.11462},
journal = {Pattern Recognition},
pages = {107957},
title = {{PILS: Exploring high-order neighborhoods by pattern mining and injection}},
url = {https://arxiv.org/pdf/1912.11462.pdf},
volume = {116},
year = {2021}
}

We introduce pattern injection local search (PILS), an optimization strategy that uses pattern mining to explore high-order local-search neighborhoods, and illustrate its application on the vehicle routing problem. PILS operates by storing a limited number of frequent patterns from elite solutions. During the local search, each pattern is used to define one move in which 1) incompatible edges are disconnected, 2) the edges defined by the pattern are reconnected, and 3) the remaining solution fragments are optimally reconnected. Each such move is accepted only in case of solution improvement. As visible in our experiments, this strategy results in a new paradigm of local search, which complements and enhances classical search approaches in a controllable amount of computational time. We demonstrate that PILS identifies useful high-order moves (e.g., 9-opt and 10-opt) which would otherwise not be found by enumeration, and that it significantly improves the performance of state-of-the-art population-based and neighborhood-centered metaheuristics.

@article{Mecler2021,
abstract = {The job sequencing and tool switching problem (SSP) has been extensively studied in the field of operations research, due to its practical relevance and methodological interest. Given a machine that can load a limited amount of tools simultaneously and a number of jobs that require a subset of the available tools, the SSP seeks a job sequence that minimizes the number of tool switches in the machine. To solve this problem, we propose a simple and efficient hybrid genetic search based on a generic solution representation, a tailored decoding operator, efficient local searches and diversity management techniques. To guide the search, we introduce a secondary objective designed to break ties. These techniques allow to explore structurally different solutions and escape local optima. As shown in our computational experiments on classical benchmark instances, our algorithm significantly outperforms all previous approaches while remaining simple to apprehend and easy to implement. We finally report results on a new set of larger instances to stimulate future research and comparative analyses.},
author = {Mecler, J. and Subramanian, A. and Vidal, T.},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Mecler, Subramanian, Vidal/Mecler, Subramanian, Vidal - 2021 - A simple and effective hybrid genetic search for the job sequencing and tool switching problem(2).pdf:pdf},
journal = {Computers {\&} Operations Research},
pages = {105153},
title = {{A simple and effective hybrid genetic search for the job sequencing and tool switching problem}},
url = {https://arxiv.org/pdf/1910.10021.pdf},
volume = {127},
year = {2021}
}

The job sequencing and tool switching problem (SSP) has been extensively studied in the field of operations research, due to its practical relevance and methodological interest. Given a machine that can load a limited amount of tools simultaneously and a number of jobs that require a subset of the available tools, the SSP seeks a job sequence that minimizes the number of tool switches in the machine. To solve this problem, we propose a simple and efficient hybrid genetic search based on a generic solution representation, a tailored decoding operator, efficient local searches and diversity management techniques. To guide the search, we introduce a secondary objective designed to break ties. These techniques allow to explore structurally different solutions and escape local optima. As shown in our computational experiments on classical benchmark instances, our algorithm significantly outperforms all previous approaches while remaining simple to apprehend and easy to implement. We finally report results on a new set of larger instances to stimulate future research and comparative analyses.

@article{Goel2020,
abstract = {The last decades have seen a tremendous amount of research being devoted to effectively managing vehicle fleets and minimizing empty mileage. However, in contrast to, e.g., the air transport sector, the question of how to best assign crews to vehicles, has received very little attention in the road transport sector. The vast majority of road freight transport in Europe is conducted by single drivers and team driving is often only conducted if there are special circumstances, e.g., security concerns. While it is clear that transport companies want to avoid the costs related to additional drivers, vehicles manned by a single driver sit unused whenever the driver takes a mandatory break or rest. Team drivers, on the other hand, can travel a much greater distance in the same amount of time, because mandatory breaks and rests are required less frequently. This paper investigates under which conditions trucking companies should use single or team driving to maximize their profitability},
author = {Goel, A. and Vidal, T. and Kok, A.L.},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Goel, Vidal, Kok/Goel, Vidal, Kok - 2021 - To team up or not Single versus team driving in European road freight transport.pdf:pdf},
journal = {Flexible Services and Manufacturing Journal},
pages = {879--913},
title = {{To team up or not: Single versus team driving in European road freight transport}},
url = {https://link.springer.com/content/pdf/10.1007/s10696-020-09398-0.pdf},
volume = {33},
year = {2021}
}

The last decades have seen a tremendous amount of research being devoted to effectively managing vehicle fleets and minimizing empty mileage. However, in contrast to, e.g., the air transport sector, the question of how to best assign crews to vehicles, has received very little attention in the road transport sector. The vast majority of road freight transport in Europe is conducted by single drivers and team driving is often only conducted if there are special circumstances, e.g., security concerns. While it is clear that transport companies want to avoid the costs related to additional drivers, vehicles manned by a single driver sit unused whenever the driver takes a mandatory break or rest. Team drivers, on the other hand, can travel a much greater distance in the same amount of time, because mandatory breaks and rests are required less frequently. This paper investigates under which conditions trucking companies should use single or team driving to maximize their profitability

@inproceedings{Parmentier2021c,
address = {Virtual},
archivePrefix = {arXiv},
arxivId = {arXiv:2106.06631v1},
author = {Parmentier, A. and Vidal, T.},
booktitle = {Proceedings of the 38th International Conference on Machine Learning},
editor = {Meila, M. and Zhang, T.},
eprint = {arXiv:2106.06631v1},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Parmentier, Vidal/Parmentier, Vidal - 2021 - Optimal counterfactual explanations in tree ensembles.pdf:pdf},
pages = {8422--8431},
publisher = {PMLR},
series = {Proceedings of Machine Learning Research},
title = {{Optimal counterfactual explanations in tree ensembles}},
url = {http://proceedings.mlr.press/v139/parmentier21a/parmentier21a.pdf},
year = {2021}
}

@inproceedings{Vidal2020a,
abstract = {The use of machine learning algorithms in finance, medicine, and criminal justice can deeply impact human lives. As a consequence, research into interpretable machine learning has rapidly grown in an attempt to better control and fix possible sources of mistakes and biases. Tree ensembles, in particular, offer a good prediction quality in various domains, but the concurrent use of multiple trees reduces the interpretability of the ensemble. Against this background, we study born-again tree ensembles, i.e., the process of constructing a single decision tree of minimum size that reproduces the exact same behavior as a given tree ensemble in its entire feature space. To find such a tree, we develop a dynamic-programming based algorithm that exploits sophisticated pruning and bounding rules to reduce the number of recursive calls. This algorithm generates optimal born-again trees for many datasets of practical interest, leading to classifiers which are typically simpler and more interpretable without any other form of compromise.},
address = {Virtual},
author = {Vidal, T. and Schiffer, M.},
booktitle = {Proceedings of the 37th International Conference on Machine Learning},
editor = {III, Hal Daum{\'{e}} and Singh, Aarti},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal, Schiffer/Vidal, Schiffer - 2020 - Born-again tree ensembles.pdf:pdf},
mendeley-groups = {Machine Learning/Decision Trees/Misc},
pages = {9743--9753},
publisher = {PMLR},
series = {Proceedings of Machine Learning Research},
title = {{Born-again tree ensembles}},
url = {http://proceedings.mlr.press/v119/vidal20a.html},
volume = {119},
year = {2020}
}

The use of machine learning algorithms in finance, medicine, and criminal justice can deeply impact human lives. As a consequence, research into interpretable machine learning has rapidly grown in an attempt to better control and fix possible sources of mistakes and biases. Tree ensembles, in particular, offer a good prediction quality in various domains, but the concurrent use of multiple trees reduces the interpretability of the ensemble. Against this background, we study born-again tree ensembles, i.e., the process of constructing a single decision tree of minimum size that reproduces the exact same behavior as a given tree ensemble in its entire feature space. To find such a tree, we develop a dynamic-programming based algorithm that exploits sophisticated pruning and bounding rules to reduce the number of recursive calls. This algorithm generates optimal born-again trees for many datasets of practical interest, leading to classifiers which are typically simpler and more interpretable without any other form of compromise.

@inproceedings{Gribel2020,
abstract = {Stochastic block models (SBMs) are often used to find assortative community structures in networks, such that the probability of connections within communities is higher than in between communities. However, classic SBMs are not limited to assortative structures. In this study, we discuss the implica- tions of this model-inherent indifference towards assortativity or disassortativity, and show that this characteristic can lead to undesirable outcomes for networks which are presupposedy assortative but which contain a reduced amount of information. To circumvent this issue, we introduce a constrained SBM that imposes strong assortativity constraints, along with efficient algorithmic approaches to solve it. These constraints significantly boost community recovery capabilities in regimes that are close to the information-theoretic threshold. They also permit to iden- tify structurally-different communities in networks representing cerebral-cortex activity regions},
archivePrefix = {arXiv},
arxivId = {arXiv:2004.11890v1},
author = {Gribel, D. and Vidal, T. and Gendreau, M.},
booktitle = {ICPR'20},
eprint = {arXiv:2004.11890v1},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Gribel, Vidal, Gendreau/Gribel, Vidal, Gendreau - 2020 - Assortative-constrained stochastic block models(2).pdf:pdf},
organization = {ArXiV: 2004.11890v1},
title = {{Assortative-constrained stochastic block models}},
url = {https://arxiv.org/pdf/2004.11890.pdf},
year = {2020}
}

Stochastic block models (SBMs) are often used to find assortative community structures in networks, such that the probability of connections within communities is higher than in between communities. However, classic SBMs are not limited to assortative structures. In this study, we discuss the implica- tions of this model-inherent indifference towards assortativity or disassortativity, and show that this characteristic can lead to undesirable outcomes for networks which are presupposedy assortative but which contain a reduced amount of information. To circumvent this issue, we introduce a constrained SBM that imposes strong assortativity constraints, along with efficient algorithmic approaches to solve it. These constraints significantly boost community recovery capabilities in regimes that are close to the information-theoretic threshold. They also permit to iden- tify structurally-different communities in networks representing cerebral-cortex activity regions

@article{Queiroga2020,
abstract = {In this paper, we are interested in the exact solution of the vehicle routing problem with back- hauls (VRPB), a classical vehicle routing variant with two types of customers: linehaul (delivery) and backhaul (pickup) ones. We propose two branch-cut-and-price (BCP) algorithms for the VRPB. The first of them follows the traditional approach with one pricing subproblem, whereas the second one exploits the linehaul/backhaul customer partitioning and defines two pricing sub- problems. The methods incorporate elements of state-of-the-art BCP algorithms, such as rounded capacity cuts, limited-memory rank-1 cuts, strong branching, route enumeration, arc elimination using reduced costs and dual stabilization. Computational experiments show that the proposed algorithms are capable of obtaining optimal solutions for all existing benchmark instances with up to 200 customers, many of them for the first time. It is observed that the approach involving two pricing subproblems is more efficient computationally than the traditional one. Moreover, new instances are also proposed for which we provide tight bounds. Also, we provide results for benchmark instances of the heterogeneous fixed fleet VRPB and the VRPB with time windows.},
author = {Queiroga, E. and Frota, Y. and Sadykov, R. and Subramanian, A. and Uchoa, E. and Vidal, T.},
doi = {10.1016/j.ejor.2020.04.047},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Queiroga et al/Queiroga et al. - 2020 - On the exact solution of vehicle routing problems with backhauls(2).pdf:pdf},
journal = {European Journal of Operational Research},
pages = {76--89},
title = {{On the exact solution of vehicle routing problems with backhauls}},
url = {https://hal.inria.fr/hal-02379008/document},
volume = {287},
year = {2020}
}

In this paper, we are interested in the exact solution of the vehicle routing problem with back- hauls (VRPB), a classical vehicle routing variant with two types of customers: linehaul (delivery) and backhaul (pickup) ones. We propose two branch-cut-and-price (BCP) algorithms for the VRPB. The first of them follows the traditional approach with one pricing subproblem, whereas the second one exploits the linehaul/backhaul customer partitioning and defines two pricing sub- problems. The methods incorporate elements of state-of-the-art BCP algorithms, such as rounded capacity cuts, limited-memory rank-1 cuts, strong branching, route enumeration, arc elimination using reduced costs and dual stabilization. Computational experiments show that the proposed algorithms are capable of obtaining optimal solutions for all existing benchmark instances with up to 200 customers, many of them for the first time. It is observed that the approach involving two pricing subproblems is more efficient computationally than the traditional one. Moreover, new instances are also proposed for which we provide tight bounds. Also, we provide results for benchmark instances of the heterogeneous fixed fleet VRPB and the VRPB with time windows.

@article{Vidal2020,
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 concise overview 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.},
author = {Vidal, T. and Laporte, G. and Matl, P.},
doi = {10.1016/j.ejor.2019.10.010},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal, Laporte, Matl/Vidal, Laporte, Matl - 2020 - A concise guide to existing and emerging vehicle routing problem variants(2).pdf:pdf},
journal = {European Journal of Operational Research},
pages = {401--416},
title = {{A concise guide to existing and emerging vehicle routing problem variants}},
url = {https://arxiv.org/pdf/1906.06750.pdf},
volume = {286},
year = {2020}
}

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 concise overview 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.

@article{Soriano2020,
abstract = {Efficiency and security are the two major concerns in cash-in-transit transportation planning. Whereas efficiency is generally achieved by finding short routes, security can be improved by generating dissimilar visit patterns. To achieve a good balance between these two objectives, the vehicle routing problem with arrival time diversification (VRPATD) aims to find optimized routing plans, over multiple periods, subject to a minimum difference between visit times at each customer. Since the customer visits are constrained by time windows and no waiting time is allowed en route, the number of feasible solutions is generally limited. To explore a larger set of feasible route options, we propose to consider alternative paths with different distances between visit locations. The resulting multigraph VRPATD better captures the characteristics of urban networks. Moreover, the extra flexibility achieved with the alternative paths helps finding better routing plans while meeting time constraints. To solve this complex problem, we introduce an adaptive large neighborhood search, which exploits piecewise-linear penalty functions for insertion evaluations, efficient local searches, and an adaptive destruction rate. This method produces remarkable results on classical instances for the simple-graph VRPATD. Moreover, our theoretical results and our experiments on real-life instances obtained from an application case in Vienna show that the multigraph problem extension leads to very significant distance savings subject to the same arrival time diversification constraints.},
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. - 2020 - The vehicle routing problem with arrival time diversification on a multigraph(2).pdf:pdf},
journal = {European Journal of Operational Research},
pages = {564--575},
title = {{The vehicle routing problem with arrival time diversification on a multigraph}},
url = {https://www.sciencedirect.com/sdfe/reader/pii/S0377221720302915/pdf},
volume = {286},
year = {2020}
}

Efficiency and security are the two major concerns in cash-in-transit transportation planning. Whereas efficiency is generally achieved by finding short routes, security can be improved by generating dissimilar visit patterns. To achieve a good balance between these two objectives, the vehicle routing problem with arrival time diversification (VRPATD) aims to find optimized routing plans, over multiple periods, subject to a minimum difference between visit times at each customer. Since the customer visits are constrained by time windows and no waiting time is allowed en route, the number of feasible solutions is generally limited. To explore a larger set of feasible route options, we propose to consider alternative paths with different distances between visit locations. The resulting multigraph VRPATD better captures the characteristics of urban networks. Moreover, the extra flexibility achieved with the alternative paths helps finding better routing plans while meeting time constraints. To solve this complex problem, we introduce an adaptive large neighborhood search, which exploits piecewise-linear penalty functions for insertion evaluations, efficient local searches, and an adaptive destruction rate. This method produces remarkable results on classical instances for the simple-graph VRPATD. Moreover, our theoretical results and our experiments on real-life instances obtained from an application case in Vienna show that the multigraph problem extension leads to very significant distance savings subject to the same arrival time diversification constraints.

@article{Homsi2019,
abstract = {Recent studies in maritime logistics have introduced a general ship routing problem and a bench- mark suite based on real shipping segments, considering pickups and deliveries, cargo selection, ship- dependent starting locations, travel times and costs, time windows, and incompatibility constraints, among other features. Together, these characteristics pose considerable challenges for exact and heuristic methods, and some cases with as few as 18 cargoes remain unsolved. To face this challenge, we propose an exact branch-and-price (B{\&}P) algorithm and a hybrid metaheuristic. Our exact method generates ele- mentary routes, but exploits decremental state-space relaxation to speed up column generation, heuris- tic strong branching, as well as advanced preprocessing and route enumeration techniques. Our meta- heuristic is a sophisticated extension of the unified hybrid genetic search. It exploits a set-partitioning phase and uses problem-tailored variation operators to efficiently handle all the problem characteristics. As shown in our experimental analyses, the B{\&}P optimally solves 239/240 existing instances within one hour. Scalability experiments on even larger problems demonstrate that it can optimally solve problems with around 60 ships and 200 cargoes (i.e., 400 pickup and delivery services) and find optimality gaps below 1.04{\%} on the largest cases with up to 260 cargoes. The hybrid metaheuristic outperforms all pre- vious heuristics and produces near-optimal solutions within minutes. These results are noteworthy, since these instances are comparable in size with the largest problems routinely solved by shipping companies.},
author = {Homsi, G. and Martinelli, R. and Vidal, T. and Fagerholt, K.},
doi = {10.1016/j.ejor.2019.11.068},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Homsi et al/Homsi et al. - 2020 - Industrial and tramp ship routing problems Closing the gap for real-scale instances(2).pdf:pdf},
journal = {European Journal of Operational Research},
pages = {972--990},
title = {{Industrial and tramp ship routing problems: Closing the gap for real-scale instances}},
url = {https://arxiv.org/pdf/1809.10584.pdf},
volume = {283},
year = {2020}
}

Recent studies in maritime logistics have introduced a general ship routing problem and a bench- mark suite based on real shipping segments, considering pickups and deliveries, cargo selection, ship- dependent starting locations, travel times and costs, time windows, and incompatibility constraints, among other features. Together, these characteristics pose considerable challenges for exact and heuristic methods, and some cases with as few as 18 cargoes remain unsolved. To face this challenge, we propose an exact branch-and-price (B&P) algorithm and a hybrid metaheuristic. Our exact method generates ele- mentary routes, but exploits decremental state-space relaxation to speed up column generation, heuris- tic strong branching, as well as advanced preprocessing and route enumeration techniques. Our meta- heuristic is a sophisticated extension of the unified hybrid genetic search. It exploits a set-partitioning phase and uses problem-tailored variation operators to efficiently handle all the problem characteristics. As shown in our experimental analyses, the B&P optimally solves 239/240 existing instances within one hour. Scalability experiments on even larger problems demonstrate that it can optimally solve problems with around 60 ships and 200 cargoes (i.e., 400 pickup and delivery services) and find optimality gaps below 1.04% on the largest cases with up to 260 cargoes. The hybrid metaheuristic outperforms all pre- vious heuristics and produces near-optimal solutions within minutes. These results are noteworthy, since these instances are comparable in size with the largest problems routinely solved by shipping companies.

@article{Kramer2020,
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.},
annote = {Breno + Italo},
author = {Kramer, R. and Iori, M. and Vidal, T.},
doi = {10.1287/ijoc.2019.0889},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Kramer, Iori, Vidal/Kramer, Iori, Vidal - 2020 - Mathematical models and search algorithms for the capacitated p-center problem(3).pdf:pdf},
journal = {INFORMS Journal on Computing},
mendeley-groups = {Teaching/INF2982-Modeling/Implementation},
number = {2},
pages = {444--460},
title = {{Mathematical models and search algorithms for the capacitated p-center problem}},
url = {https://arxiv.org/pdf/1803.04865.pdf},
volume = {32},
year = {2020}
}

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.

@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},
mendeley-groups = {Teaching/INF2982-Modeling/Implementation},
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.

@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 - Sustainable city logistics via access restrictions An impact assessment of city center policies(2).pdf:pdf},
institution = {University of Vienna, Austria},
title = {{Sustainable city logistics via access restrictions? An impact assessment of city center policies}},
year = {2019}
}

@article{Borthen2019,
abstract = {This paper introduces a bi-objective model for the offshore supply vessel planning problem (SVPP) in the oil {\&} gas industry. The SVPP consists of determining a new weekly plan for sailing the platform supply vessels whenever the sailing plan needs revising due to some major events, such as the arrival or re- moval of drilling rigs, and demand increase or reduction in the current platforms. Apart from remaining cost-efficient, the new weekly plan is required to be persistent , i.e., exhibiting few changes from the pre- vious plan. To achieve this, we propose a bi-objective optimization framework that enables the planners to simultaneously take into account both costs and persistence-related objectives. The framework encom- passes a bi-objective SVPP model and a genetic search algorithm adapted from Borthen et al. (2018). We show that the proposed algorithm is able to provide high-quality solutions in reasonable time and has the decision support capability in real offshore operation planning.},
author = {Borthen, T. and Loennechen, H. and Fagerholt, K. and Wang, X. and Vidal, T.},
doi = {10.1016/j.cor.2019.06.014},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Borthen et al/Borthen et al. - 2019 - Bi-objective offshore supply vessel planning with costs and persistence objectives(2).pdf:pdf},
journal = {Computers {\&} Operations Research},
pages = {285--296},
title = {{Bi-objective offshore supply vessel planning with costs and persistence objectives}},
url = {https://www.sciencedirect.com/science/article/pii/S0305054819301741/pdfft?md5=6c42b3c9091f90784cc45756553906e7{\&}pid=1-s2.0-S0305054819301741-main.pdf},
volume = {111},
year = {2019}
}

This paper introduces a bi-objective model for the offshore supply vessel planning problem (SVPP) in the oil & gas industry. The SVPP consists of determining a new weekly plan for sailing the platform supply vessels whenever the sailing plan needs revising due to some major events, such as the arrival or re- moval of drilling rigs, and demand increase or reduction in the current platforms. Apart from remaining cost-efficient, the new weekly plan is required to be persistent , i.e., exhibiting few changes from the pre- vious plan. To achieve this, we propose a bi-objective optimization framework that enables the planners to simultaneously take into account both costs and persistence-related objectives. The framework encom- passes a bi-objective SVPP model and a genetic search algorithm adapted from Borthen et al. (2018). We show that the proposed algorithm is able to provide high-quality solutions in reasonable time and has the decision support capability in real offshore operation planning.

@article{Matl2019,
abstract = {After decades of intensive research on the vehicle routing problem (VRP), many highly efficient single-objective heuristics exist for a multitude of VRP variants. But when new side-objectives emerge—such as service quality, workload balance, pollution reduction, consistency—the prevailing approach has been to develop new, problem-specific, and increasingly complex multiobjective (MO) methods. Yet in principle, MO problems can be efficiently solved with existing single-objective solvers. This is the fundamental idea behind the well-known epsilon-constraint method (ECM). Despite its generality and conceptual simplicity, the ECM has been largely ignored in the domain of heuristics and remains associated mostly with exact algorithms. In this article, we dispel these preconceptions and demonstrate that epsilon-constraint- based frameworks can be a highly effective way to directly leverage the decades of research on single-objective VRP heuristics in emerging MO settings.},
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}},
url = {https://arxiv.org/pdf/1705.10174.pdf},
volume = {73},
year = {2019}
}

After decades of intensive research on the vehicle routing problem (VRP), many highly efficient single-objective heuristics exist for a multitude of VRP variants. But when new side-objectives emerge—such as service quality, workload balance, pollution reduction, consistency—the prevailing approach has been to develop new, problem-specific, and increasingly complex multiobjective (MO) methods. Yet in principle, MO problems can be efficiently solved with existing single-objective solvers. This is the fundamental idea behind the well-known epsilon-constraint method (ECM). Despite its generality and conceptual simplicity, the ECM has been largely ignored in the domain of heuristics and remains associated mostly with exact algorithms. In this article, we dispel these preconceptions and demonstrate that epsilon-constraint- based frameworks can be a highly effective way to directly leverage the decades of research on single-objective VRP heuristics in emerging MO settings.

@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.

@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

@article{Breunig2019,
abstract = {Two-echelon distribution systems are attractive from an economical standpoint and help to keep large vehicles out of densely populated city centers. Large trucks can be used to deliver goods to intermediate facilities in accessible locations, whereas smaller vehicles allow to reach the final customers. Due to their reduced size, pollution, and noise, multiple companies consider using an electric fleet of terrestrial or aerial vehicles for last-mile deliveries. Route planning in multi-tier logistics leads to notoriously difficult problems. This difficulty is accrued in the presence of an electric fleet since each vehicle operates on a smaller range and may require planned visits to recharging stations. To study these challenges, we introduce the electric two-echelon vehicle routing problem (E2EVRP) as a prototypical problem. We propose a large neighborhood search (LNS) metaheuristic as well as an exact mathematical programming algorithm, which uses decomposi- tion techniques to enumerate promising first-level solutions in conjunction with bounding functions and route enumeration for the second-level routes. These algorithms produce optimal or near-optimal so- lutions for the problem and allow us to evaluate the impact of several defining features of optimized battery-powered distribution networks. We created representative E2EVRP benchmark instances to simulate realistic metropolitan areas. In particular, we observe that the detour miles due to recharging decrease proportionally to 1/ $\rho$x with x ≈5/4 as a function of the charging stations density $\rho$; e.g., in a scenario where the density of charging stations is doubled, recharging detours are reduced by 58{\%}. Finally, we evaluate the trade-off between battery capacity and detour miles. This estimate is critical for strategic fleet-acquisition decisions, in a context where large batteries are generally more costly and less environment-friendly.},
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}
}

Two-echelon distribution systems are attractive from an economical standpoint and help to keep large vehicles out of densely populated city centers. Large trucks can be used to deliver goods to intermediate facilities in accessible locations, whereas smaller vehicles allow to reach the final customers. Due to their reduced size, pollution, and noise, multiple companies consider using an electric fleet of terrestrial or aerial vehicles for last-mile deliveries. Route planning in multi-tier logistics leads to notoriously difficult problems. This difficulty is accrued in the presence of an electric fleet since each vehicle operates on a smaller range and may require planned visits to recharging stations. To study these challenges, we introduce the electric two-echelon vehicle routing problem (E2EVRP) as a prototypical problem. We propose a large neighborhood search (LNS) metaheuristic as well as an exact mathematical programming algorithm, which uses decomposi- tion techniques to enumerate promising first-level solutions in conjunction with bounding functions and route enumeration for the second-level routes. These algorithms produce optimal or near-optimal so- lutions for the problem and allow us to evaluate the impact of several defining features of optimized battery-powered distribution networks. We created representative E2EVRP benchmark instances to simulate realistic metropolitan areas. In particular, we observe that the detour miles due to recharging decrease proportionally to 1/ $ρ$x with x ≈5/4 as a function of the charging stations density $ρ$; e.g., in a scenario where the density of charging stations is doubled, recharging detours are reduced by 58%. Finally, we evaluate the trade-off between battery capacity and detour miles. This estimate is critical for strategic fleet-acquisition decisions, in a context where large batteries are generally more costly and less environment-friendly.

@article{Matl2018a,
abstract = {In practical vehicle routing problems (VRPs), important non-monetary benefits can be achieved with more balanced operational plans that explicitly consider workload equity. This has motivated practitioners to include a wide variety of balancing criteria in decision support systems, and researchers to examine the properties of these criteria and the trade-offs made when optimizing them. As a result, previous studies have provided a much-needed understanding of how different equity functions affect the resulting VRP solutions. However, by focusing exclusively on models that balance tour lengths, a critical aspect has thus far remained unexplored — namely the impact of the workload resource subject to the balancing. In this work, we generalize previous studies to different workload resources, extend the scope of those analyses to additional aspects of managerial and methodological significance, and reevaluate accordingly previous conclusions and guidelines for formulating a balance criterion. Overall, our study counter-balances the focus of previous works and reveals the importance of selecting the right workload resource. Although the marginal cost of equity is low for all the examined models, the trade-off structure depends primarily on the workload resource, and less on the equity function. For the same resource, we observe a notable degree of overlap between the solutions found with different equity functions. Moreover, we find that there typically exists a set of low-cost VRP solutions that are well-balanced on average with respect to all the examined balance criteria. However, they are difficult to identify in practice as they are mostly Pareto-dominated by solutions optimized with respect to any single criterion. Finally, we observe that solutions with similar cost and balance tend to exhibit similar solution structure, a property that should be directly exploited by optimization methods.},
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}
}

In practical vehicle routing problems (VRPs), important non-monetary benefits can be achieved with more balanced operational plans that explicitly consider workload equity. This has motivated practitioners to include a wide variety of balancing criteria in decision support systems, and researchers to examine the properties of these criteria and the trade-offs made when optimizing them. As a result, previous studies have provided a much-needed understanding of how different equity functions affect the resulting VRP solutions. However, by focusing exclusively on models that balance tour lengths, a critical aspect has thus far remained unexplored — namely the impact of the workload resource subject to the balancing. In this work, we generalize previous studies to different workload resources, extend the scope of those analyses to additional aspects of managerial and methodological significance, and reevaluate accordingly previous conclusions and guidelines for formulating a balance criterion. Overall, our study counter-balances the focus of previous works and reveals the importance of selecting the right workload resource. Although the marginal cost of equity is low for all the examined models, the trade-off structure depends primarily on the workload resource, and less on the equity function. For the same resource, we observe a notable degree of overlap between the solutions found with different equity functions. Moreover, we find that there typically exists a set of low-cost VRP solutions that are well-balanced on average with respect to all the examined balance criteria. However, they are difficult to identify in practice as they are mostly Pareto-dominated by solutions optimized with respect to any single criterion. Finally, we observe that solutions with similar cost and balance tend to exhibit similar solution structure, a property that should be directly exploited by optimization methods.

@article{Hiermann2019,
abstract = {We introduce an electric vehicle routing problem combining conventional, plug-in hybrid, and electric ve- hicles. Electric vehicles are constrained in their service range by their battery capacity, and may require time-consuming recharging operations at some specific locations. Plug-in hybrid vehicles have two en- gines, an internal combustion engine and an electric engine using a built-in rechargeable battery. These vehicles can avoid visits to recharging stations by switching to fossil fuel. However, this flexibility comes at the price of a generally higher consumption rate and utility cost. To solve this complex problem variant, we design a sophisticated metaheuristic which combines a genetic algorithm with local and large neighborhood search. All route evaluations, within the approach, are based on a layered optimization algorithm which combines labeling techniques and greedy evaluation policies to insert recharging stations visits in a fixed trip and select the fuel types. The metaheuristic is finally hybridized with an integer programming solver, over a set partitioning formulation, so as to recombine high-quality routes from the search history into better solutions. Extensive experimental analyses are conducted, highlighting the good performance of the algorithm and the contribution of each of its main components. Finally, we investigate the impact of fuel and energy cost on fleet composition decisions. Our experiments show that a careful use of a mixed fleet can significantly reduce operational costs in a large variety of price scenarios, in comparison with the use of a fleet composed of a single vehicle class.},
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}
}

We introduce an electric vehicle routing problem combining conventional, plug-in hybrid, and electric ve- hicles. Electric vehicles are constrained in their service range by their battery capacity, and may require time-consuming recharging operations at some specific locations. Plug-in hybrid vehicles have two en- gines, an internal combustion engine and an electric engine using a built-in rechargeable battery. These vehicles can avoid visits to recharging stations by switching to fossil fuel. However, this flexibility comes at the price of a generally higher consumption rate and utility cost. To solve this complex problem variant, we design a sophisticated metaheuristic which combines a genetic algorithm with local and large neighborhood search. All route evaluations, within the approach, are based on a layered optimization algorithm which combines labeling techniques and greedy evaluation policies to insert recharging stations visits in a fixed trip and select the fuel types. The metaheuristic is finally hybridized with an integer programming solver, over a set partitioning formulation, so as to recombine high-quality routes from the search history into better solutions. Extensive experimental analyses are conducted, highlighting the good performance of the algorithm and the contribution of each of its main components. Finally, we investigate the impact of fuel and energy cost on fleet composition decisions. Our experiments show that a careful use of a mixed fleet can significantly reduce operational costs in a large variety of price scenarios, in comparison with the use of a fleet composed of a single vehicle class.

@article{Penna2019,
abstract = {We consider a family of rich vehicle routing problems (RVRP) which have the particularity to combine a heterogeneous fleet with other attributes, such as backhauls, multi- ple depots, split deliveries, site dependency, open routes, duration limits, and time windows. To efficiently solve these problems, we propose a hybrid metaheuristic which combines an iterated local search with variable neighborhood descent, for solution improvement, and a set partitioning formulation, to exploit the memory of the past search. Moreover, we investigate a class of combined neighborhoods which jointly modify the sequences of visits and perform either heuristic or optimal reassignments of vehicles to routes. To the best of our knowledge, this is the first unified approach for a large class of heterogeneous fleet RVRPs, capable of solving more than 12 problem variants. The efficiency of the algorithm is evaluated on 643 well-known benchmark instances, and 71.70{\%} of the best known solutions are either retrieved or improved. Moreover, the proposed metaheuristic, which can be considered as a matheuristic, produces high quality solutions with low standard deviation in comparison with previous methods. Finally, we observe that the use of combined neighborhoods does not lead to significant quality gains. Contrary to intuition, the computational effort seems better spent on more intensive route optimization rather than on more intelligent and frequent fleet re-assignments.},
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}
}

We consider a family of rich vehicle routing problems (RVRP) which have the particularity to combine a heterogeneous fleet with other attributes, such as backhauls, multi- ple depots, split deliveries, site dependency, open routes, duration limits, and time windows. To efficiently solve these problems, we propose a hybrid metaheuristic which combines an iterated local search with variable neighborhood descent, for solution improvement, and a set partitioning formulation, to exploit the memory of the past search. Moreover, we investigate a class of combined neighborhoods which jointly modify the sequences of visits and perform either heuristic or optimal reassignments of vehicles to routes. To the best of our knowledge, this is the first unified approach for a large class of heterogeneous fleet RVRPs, capable of solving more than 12 problem variants. The efficiency of the algorithm is evaluated on 643 well-known benchmark instances, and 71.70% of the best known solutions are either retrieved or improved. Moreover, the proposed metaheuristic, which can be considered as a matheuristic, produces high quality solutions with low standard deviation in comparison with previous methods. Finally, we observe that the use of combined neighborhoods does not lead to significant quality gains. Contrary to intuition, the computational effort seems better spent on more intensive route optimization rather than on more intelligent and frequent fleet re-assignments.

@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},
mendeley-groups = {Joao-Paper},
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 $}\epsilon{$-approximate solution for the continuous version of the problem in $}\mathcal{\{}O{\}}(n \log m \log \frac{\{}n B{\}}{\{}\epsilon{\}}){$ operations and an integer solution in $}\mathcal{\{}O{\}}(n \log m \log B){$, where $}n{$ is the number of decision variables, $}m{$ is the number of constraints, and $}B{$ is the resource bound. A complexity of $}\mathcal{\{}O{\}}(n \log 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.

@article{Bui2019,
abstract = {We investigate how to partition a rectangular region of length L1 and height L2 into n rectangles of given areas (a1,..., an) using two-stage guillotine cuts, so as to minimize either (i) the sum of the perimeters, (ii) the largest perimeter, or (iii) the maximum aspect ratio of the rectangles. These problems play an important role in the ongoing Vietnamese land-allocation reform, as well as in the optimization ofmatrix multiplication algorithms.We show that the first problem can be solved to optimality in O(n log n), while the two others are NP-hard. We propose mixed integer linear programming formulations and a binary search- based approach for solving the NP-hard problems. Experimental analyses are conducted to compare the solution approaches in terms of computational efficiency and solution quality, for different objectives.},
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},
pages = {45--62},
title = {{On three soft rectangle packing problems with guillotine constraints}},
url = {https://arxiv.org/pdf/1805.03631.pdf},
volume = {74},
year = {2019}
}

We investigate how to partition a rectangular region of length L1 and height L2 into n rectangles of given areas (a1,..., an) using two-stage guillotine cuts, so as to minimize either (i) the sum of the perimeters, (ii) the largest perimeter, or (iii) the maximum aspect ratio of the rectangles. These problems play an important role in the ongoing Vietnamese land-allocation reform, as well as in the optimization ofmatrix multiplication algorithms.We show that the first problem can be solved to optimality in O(n log n), while the two others are NP-hard. We propose mixed integer linear programming formulations and a binary search- based approach for solving the NP-hard problems. Experimental analyses are conducted to compare the solution approaches in terms of computational efficiency and solution quality, for different objectives.

@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.},
annote = {1. Matheus Suknaic
2. Gabriel},
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},
mendeley-groups = {Teaching/INF2982-Modeling/Paper-Analysis,Teaching/INF2982-Modeling/Implementation},
number = {3},
pages = {527--543},
title = {{Two-dimensional phase unwrapping via balanced spanning forests}},
url = {https://arxiv.org/pdf/1812.08277.pdf},
volume = {31},
year = {2019}
}

Phase unwrapping is the process of recovering a continuous phase signal from an original signal wrapped in the (−$π$,$π$] 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.

@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}
}

@article{Haddad2018,
abstract = {We consider the multi-vehicle one-to-one pickup and delivery problem with split loads, a NP-hard prob- lem linked with a variety of applications for bulk product transportation, bike-sharing systems and inven- tory re-balancing. This problem is notoriously difficult due to the interaction of two challenging vehicle routing attributes, “pickups and deliveries” and “split deliveries”. This possibly leads to optimal solutions of a size that grows exponentially with the instance size, containing multiple visits per customer pair, even in the same route. To solve this problem, we propose an iterated local search metaheuristic as well as a branch-and-price algorithm. The core of the metaheuristic consists of a new large neighborhood search, which reduces the problem of finding the best insertion combination of a pickup and delivery pair into a route (with possible splits) to a resource-constrained shortest path and knapsack problem. Similarly, the branch-and-price algorithm uses sophisticated labeling techniques, route relaxations, pre- processing and branching rules for an efficient resolution. Our computational experiments on classical single-vehicle instances demonstrate the excellent performance of the metaheuristic, which produces new best known solutions for 92 out of 93 test instances, and outperforms all previous algorithms. Experimen- tal results on new multi-vehicle instances with distance constraints are also reported. The branch-and- price algorithm produces optimal solutions for instances with up to 20 pickup-and-delivery pairs, and very accurate solutions are found by the metaheuristic.},
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 loa(2).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}
}

We consider the multi-vehicle one-to-one pickup and delivery problem with split loads, a NP-hard prob- lem linked with a variety of applications for bulk product transportation, bike-sharing systems and inven- tory re-balancing. This problem is notoriously difficult due to the interaction of two challenging vehicle routing attributes, “pickups and deliveries” and “split deliveries”. This possibly leads to optimal solutions of a size that grows exponentially with the instance size, containing multiple visits per customer pair, even in the same route. To solve this problem, we propose an iterated local search metaheuristic as well as a branch-and-price algorithm. The core of the metaheuristic consists of a new large neighborhood search, which reduces the problem of finding the best insertion combination of a pickup and delivery pair into a route (with possible splits) to a resource-constrained shortest path and knapsack problem. Similarly, the branch-and-price algorithm uses sophisticated labeling techniques, route relaxations, pre- processing and branching rules for an efficient resolution. Our computational experiments on classical single-vehicle instances demonstrate the excellent performance of the metaheuristic, which produces new best known solutions for 92 out of 93 test instances, and outperforms all previous algorithms. Experimen- tal results on new multi-vehicle instances with distance constraints are also reported. The branch-and- price algorithm produces optimal solutions for instances with up to 20 pickup-and-delivery pairs, and very accurate solutions are found by the metaheuristic.

@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.

@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.},
annote = {Cleber + Ian},
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},
mendeley-groups = {Teaching/INF2982-Modeling/Implementation},
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.

@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.

@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.

@article{Capua2018,
abstract = {We propose an iterated local search based on several classes of local and large neighborhoods for the bin packing problem with conflicts. This problem, which combines the characteristics of both bin packing and vertex coloring, arises in vari- ous application contexts such as logistics and transportation, timetabling, and resource allocation for cloud computing.We introduceO(1) evaluation procedures for classical local-search moves, polynomial variants of ejection chains and assignment neighbor- hoods, an adaptive set covering-based neighborhood, and finally a controlled use of 0-cost moves to further diversify the search. The overall method produces solutions of good quality on the classical benchmark instances and scales very well with an increase of problem size. Extensive computational experiments are conducted to measure the respective contribution ofeach proposed neighborhood. In particular, the 0-cost moves and the large neighborhood based on set covering contribute very significantly to the search. Several research perspectives are open in relation to possible hybridizations with other state-of-the-art mathematical programming heuristics for this problem.},
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}
}

We propose an iterated local search based on several classes of local and large neighborhoods for the bin packing problem with conflicts. This problem, which combines the characteristics of both bin packing and vertex coloring, arises in vari- ous application contexts such as logistics and transportation, timetabling, and resource allocation for cloud computing.We introduceO(1) evaluation procedures for classical local-search moves, polynomial variants of ejection chains and assignment neighbor- hoods, an adaptive set covering-based neighborhood, and finally a controlled use of 0-cost moves to further diversify the search. The overall method produces solutions of good quality on the classical benchmark instances and scales very well with an increase of problem size. Extensive computational experiments are conducted to measure the respective contribution ofeach proposed neighborhood. In particular, the 0-cost moves and the large neighborhood based on set covering contribute very significantly to the search. Several research perspectives are open in relation to possible hybridizations with other state-of-the-art mathematical programming heuristics for this problem.

@article{Matl2018,
abstract = {Over the past two decades, equity aspects have been considered in a grow- ing number of models and methods for vehicle routing problems (VRPs). Equity con- cerns most often relate to fairly allocating workloads and to balancing the utilization of resources, and many practical applications have been reported in the literature. How- ever, there has been only limited discussion about how workload equity should be mod- eled in the context of VRPs, and various measures for optimizing such objectives have been proposed and implemented without a critical evaluation of their respective mer- its and consequences. This article addresses this gap by providing an analysis of classical and alternative equity functions for biobjective VRP models. In our survey, we review and categorize the existing literature on equitable VRPs. In the analysis, we identify a set of axiomatic properties that an ideal equity measure should satisfy, collect six common measures of equity, and point out important connections between their properties and the properties of the resulting Pareto-optimal solutions. To gauge the extent of these impli- cations, we also conduct a numerical study on small biobjective VRP instances solvable to optimality. Our study reveals two undesirable consequences when optimizing equity with nonmonotonic functions: Pareto-optimal solutions can consist of non-TSP-optimal tours, and even if all tours are TSP optimal, Pareto-optimal solutions can be workload inconsistent, i.e., composed of tours whose workloads are all equal to or longer than those of other Pareto-optimal solutions.We show that the extent of these phenomena should not be underestimated. The results of our biobjective analysis remain valid also for weighted sum, constraint-based, or single-objective models. Based on this analysis, we conclude that monotonic equity functions are more appropriate for certain types of VRP models, and suggest promising avenues for further research on equity in logistics.},
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}
}

Over the past two decades, equity aspects have been considered in a grow- ing number of models and methods for vehicle routing problems (VRPs). Equity con- cerns most often relate to fairly allocating workloads and to balancing the utilization of resources, and many practical applications have been reported in the literature. How- ever, there has been only limited discussion about how workload equity should be mod- eled in the context of VRPs, and various measures for optimizing such objectives have been proposed and implemented without a critical evaluation of their respective mer- its and consequences. This article addresses this gap by providing an analysis of classical and alternative equity functions for biobjective VRP models. In our survey, we review and categorize the existing literature on equitable VRPs. In the analysis, we identify a set of axiomatic properties that an ideal equity measure should satisfy, collect six common measures of equity, and point out important connections between their properties and the properties of the resulting Pareto-optimal solutions. To gauge the extent of these impli- cations, we also conduct a numerical study on small biobjective VRP instances solvable to optimality. Our study reveals two undesirable consequences when optimizing equity with nonmonotonic functions: Pareto-optimal solutions can consist of non-TSP-optimal tours, and even if all tours are TSP optimal, Pareto-optimal solutions can be workload inconsistent, i.e., composed of tours whose workloads are all equal to or longer than those of other Pareto-optimal solutions.We show that the extent of these phenomena should not be underestimated. The results of our biobjective analysis remain valid also for weighted sum, constraint-based, or single-objective models. Based on this analysis, we conclude that monotonic equity functions are more appropriate for certain types of VRP models, and suggest promising avenues for further research on equity in logistics.

@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}
}

@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.

@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.

@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.

@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.

@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.

@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},
mendeley-groups = {Joao-Paper},
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 \log m \log (B/n)){$, and the complexity of obtaining an $}\epsilon{$-approximate solution for the continuous case is $}O(n \log m \log (B/\epsilon)){$, $}n{$ being the number of variables, $}m{$ the number of ascending constraints (such that $}m {\textless} n{$), $}\epsilon{$ a desired precision, and $}B{$ the total resource. This algorithm attains the best-known complexity when $}m = n{$, and improves it when $}\log m = o(\log 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.

@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.

@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.

@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.

@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.

@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.

@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.

@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.

@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.

@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.},
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.

@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.

@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.

@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.

@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

@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.

@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.

@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}
}

@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.

@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.

@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.

@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(2).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,Teaching/INF2980-VRP-Project},
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.