showing 4 related works from this author
Large multiple neighborhood search for the clustered vehicle-routing problem
2018
Abstract The clustered vehicle-routing problem is a variant of the classical capacitated vehicle-routing problem in which customers are partitioned into clusters, and it is assumed that each cluster must have been served completely before the next cluster is served. This decomposes the problem into three subproblems, i.e., the assignment of clusters to routes, the routing inside each cluster, and the sequencing of the clusters in the routes. The second task requires the solution of several Hamiltonian path problems, one for each possibility to route through the cluster. We pre-compute the Hamiltonian paths for every pair of customers of each cluster. We present a large multiple neighborhood…
Large multiple neighborhood search for the soft-clustered vehicle-routing problem
2021
Abstract The soft-clustered vehicle-routing problem (SoftCluVRP) is a variant of the classical capacitated vehicle-routing problem. Customers are partitioned into clusters and all customers of the same cluster must be served by the same vehicle. In this paper, we present a large multiple neighborhood search for the SoftCluVRP. We design and analyze multiple cluster destroy and repair operators as well as two post-optimization components, which are both based on variable neighborhood descent. The first allows inter-route exchanges of complete clusters, while the second searches for intra-route improvements by combining classical neighborhoods (2-opt, Or-opt, double-bridge) and the Balas-Simo…
Branch-Price-and-Cut for the Soft-Clustered Capacitated Arc-Routing Problem
2021
The soft-clustered capacitated arc-routing problem (SoftCluCARP) is a variant of the classical capacitated arc-routing problem. The only additional constraint is that the set of required edges, that is, the streets to be serviced, is partitioned into clusters, and feasible routes must respect the soft-cluster constraint, that is, all required edges of the same cluster must be served by the same vehicle. In this article, we design an effective branch-price-and-cut algorithm for the exact solution of the SoftCluCARP. Its new components are a metaheuristic and branch-and-cut-based solvers for the solution of the column-generation subproblem, which is a profitable rural clustered postman tour …
Exact solution of the soft-clustered vehicle-routing problem
2020
Abstract The soft-clustered vehicle-routing problem (SoftCluVRP) extends the classical capacitated vehicle-routing problem by one additional constraint: The customers are partitioned into clusters and feasible routes must respect the soft-cluster constraint, that is, all customers of the same cluster must be served by the same vehicle. In this article, we design and analyze different branch-and-price algorithms for the exact solution of the SoftCluVRP. The algorithms differ in the way the column-generation subproblem, a variant of the shortest-path problem with resource constraints (SPPRC), is solved. The standard approach for SPPRCs is based on dynamic-programming labeling algorithms. We s…