Workshop Details

[Video]

[Video]

We propose a novel repositioning strategy that is combined with a nearest assignment heuristic to solve the dynamic ride-hailing problem. The service area is divided into multiple overlapping circular zones, representing the potential customer locations that can be reached from a given parking lot within the required pickup time of 5 minutes. For each zone, a demand estimation and a supply calculation are performed. Based on a Poisson distribution, the undersupply probability for each zone can be determined. Combined with the expected reward per request in each zone and the repositioning costs of any available vehicle, strategic repositioning can be performed to balance supply and demand. The results show the effectiveness of the proposed approach, especially for small fleets.

[Challenge Paper]  [Video]

This paper summarizes our work on implementing solutions for the ride-hailing problem proposed by the DIMACS Vehicle Routing problems implementation challenge. The main focus of our solution has been the use of attention mechanisms and reinforcement learning. The implemented algorithms produced competitive results, but could benefit from further improvement regarding accuracy and running time on large instances.

[Challenge Paper]   [Video]

This paper describes FSP4D, an effective approach for the solution of Capacitated Vehicle Routing Problem instances primarily designed for the 12th DIMACS implementation challenge. FSP4D employs an iterative part in which a fast optimization based on the iterated local search paradigm is combined with a simulated annealing diversification strategy. During this part, routes are collected into a pool. A set partitioning heuristic is then used to identify high-quality combinations of these routes. The iterative optimization and the set partitioning resolution are repeated several times following a repetitive schema. Experimental results show that the proposed approach is able to obtain small average primal integral values for most of the benchmark instances tested.

[Challenge Paper]   [Video]

In this paper we propose a hybrid metaheuristic for the Capacitated Vehicle Routing Problem (CVRP) called Hybrid Genetic Search with Ruin-and-Recreate (HGSRR). The CVRP is a problem that has been subject to intense research efforts for more than sixty years. Yet, significant algorithmic improvements are still being made. The most competitive heuristic solution algorithms of today utilize, and often combine, strategies and elements from evolutionary algorithms, local search, and ruin-and-recreate based large neighborhood search. The proposed method HGSRR is no exception, as it is based on the hybrid genetic search algorithm proposed by [8], although it differs by applying the ruin-and-recreate based large neighborhood search from [1] to extend the education phase of the genetic algorithm.

[Challenge Paper]   [Video]

This report describes the solver POP-HGS implemented by EQRS team to participate in the CVRP track of the 12th DIMACS Implementation Challenge. The method is a Partial OPtimization Metaheuristic Under Special Intensification Conditions (POPMUSIC), where the subproblems are solved by the state-of-the-art hybrid genetic search for the CVRP (HGS-CVRP).

[Challenge Paper]   [Video]

The hybrid genetic search (HGS) metaheuristic has produced outstanding results for several variants of the vehicle routing problem. A recent implementation of HGS specialized to the capacitated vehicle routing problem (CVRP) stands as a state-of-the-art method for this variant. This paper proposes an improved HGS for the CVRP obtained by incorporating a new method for initializing the population to guide the search more efficiently and effectively. The initialization method introduced in this work combines an approach based on frequent patterns extracted from good solutions by a data mining process and a randomized version of the Clarke and Wright savings heuristic. As observed in our experimental comparison with the original algorithm, the proposed method provides significant improvements to the primal integral, a performance measure that rewards a balance of convergence speed and solution quality.

[Challenge Paper]   [Video]

We propose a Fast Heuristic Solver with Dynamic route number adjustment(FHDSolver) to solve vehicle routing problem with time windows(VRPTW) quickly and efficiently under the rule of DIMACS Challenge. Our approach uses an advanced route number selection mechanism, and the experiment results and final rankings have demonstrated the superiority of our algorithm

[Challenge Paper]   [Video].

This paper describes a high-performance implementation of Hybrid Genetic Search (HGS) for the Vehicle Routing Problem with Time Windows (VRPTW) [11]. We added time window support to the state-of-the-art open-source implementation of HGS for the Capacitated Vehicle Routing Problem (HGS-CVRP) [10], and included additional construction heuristics, a Selective Route Exchange (SREX) [6] crossover and an intensified local search procedure inspired by the SWAP* neighborhood [11]. The code has been optimized and we used different schedules for growing the size of neighborhood and population based on instance characteristics. For the VRPTW with distance-only objective (not minimizing vehicles) we found several improvements of best known solutions (BKS) for Gehring & Homberger [3] benchmark instances. The solver ranked 1st in Phase 1 of the VRPTW track of the 12th DIMACS implementation challenge.

[Challenge Paper]   [Video]

This paper describes the ALNS++ heuristic that participated in DIMACS Vehicle Routing implementation challenge. The heuristic has been applied to the Capacitated Vehicle Routing Problem (CVRP), the Vehicle Routing Problem with Time Windows (VRPTW), the Capacitated Arc Routing Problem (CARP) and the Node, Edge, Arc Routing Problem (NEARP). The heuristic produce promising results in the computational experiments.

[Challenge Paper]   [Video]

We try to provide a historical perspective on the development of metaheuristics applied to vehicle routing problems since the late 1980's. The talk will cover both trajectory-based methods (e.g., Tabu Search) and population-based ones (e.g., Genetic Algorithms). Our main focus will be the Capacitated VRP, but we will mention other problems.

[Video]

The multi-vehicle inventory routing problem (MIRP) tackles the combination of inventory management and vehicle routing, which is a challenging NP-hard optimization problem. It seeks a minimum-cost solution which utilizes a fleet to perform deliveries in multiple periods, ensuring that no customer runs out of stock. We propose a three-stage matheuristic (TSMH) consists of three optimization stages to solve the MIRP. The first stage optimizes the global delivery schedule and generates a feasible initial solution by a relax-and-repair method. The second stage improves the initial solution by iteratively improving the local structure of the delivery schedule. The last stage adopts a solution-based tabu search for the MIRP to implement a detailed optimization. The experimental results on commonly-used instances show that the proposed algorithm can find new upper bounds on 100 out of the 640 small instances and 192 out of the 240 large ones. These results demonstrate that the TSMH is competitive in solving the large-scale MIRP.

[Challenge Paper]   [Video]

In this paper, we propose a branch-and-cut (B&C) method for the inventory routing problem using an efficient matheuristic to warm-start it. The B&C part of the algorithm is based on the known customer schedule formulation, but where we propose a modification that drastically reduces the number of customer schedules. The matheuristic has already proved effective on the inventory routing problem, but we propose several extensions that further improve the solution quality. In the construction phase of the matheuristic, we propose a second method to generate more diverse routes used to create an initial feasible solution. In addition, we expand the solution space of the improvement phase of the matheuristic, leading to a better starting point for the B&C method. We have tested the proposed solution method on the 1038 DIMACS instances, proving optimality and finding new best-known solutions on 278 and 254 instances, respectively.

[Challenge Paper]   [Video]

We propose a new branch-and-cut scheme with modular mechanisms to recover feasibility and improve even partial solutions, by reorganizing delivery routes and optimizing inventory flows. Our algorithm employs a decision tree to select either aggregated or disaggregated formulations, according to the number of periods, vehicles, and customers. Due to the hardware used, computational experiments ran up to 1620 seconds, and our method was able to find 342 optimal solutions among 1038 feasible instances solved within this time.

Inventory Routing Problems (IRP) are among the hardest extension of a VRP. One of its challenges is how to grasp the connection among the periods where the inventory and routing take place. We extend a two-stage matheuristic which iteratively solves the routing problem in the first stage using a metaheuristic and the inventory problem in the second stage using an exact algorithm. After defining the visits of each route for each period, the inventory problem can be modeled as a network flow problem. Our approach’s main contribution is how to efficiently hot start the resolution of each network flow. The resulting algorithm performs promisingly on the classical benchmark set compared to other literature approaches. The algorithm was able to find 302 new best-known solutions out of the 1038 instances. This success suggests the highly efficient inventory stage resolution allows current metaheuristics to solve IRPs similarly to how they do on single period VRPs, obtaining solutions comparable in quality.

[Challenge Paper]   [Video]

This paper addresses the capacitated vehicle routing problem(CVRP). We propose a Fast Hybrid CVRP Solver(FHCSolver) to find the solutions quickly and efficiently under the rule of DIMACS Challenge, combined with Fast ILS Localized Optimization and Hybrid Genetic Search. The experiment results and final rankings have demonstrated the superiority of our algorithm.

[Challenge Paper]   [Video]

This document describes the solver MAESN, submitted to the CVRP track of the 12th DIMACS Implementation Challenge.

[Challenge Paper]   [Video]

This paper presents an extension of Adaptive Iterated Local Search (AILS), a recently proposed metaheuristic. This version, called AILS-II, tackles the so-called exploration and exploitation traits of metaheuristics in a two-phase method. While the first phase is a more exploratory searching phase, the second exploits the regions of the best solutions found during the search. Computational experiments with benchmark instances show that AILS-II consistently outperforms the other methods in larger instances being highly competitive in smaller instances.

[Video]

We present an effective metaheuristic framework based on the recently proposed hybrid adaptive large neighborhood search (HALNS) for the vehicle routing problem (VRP) with availability profiles and VRPs with depot location decisions. The HALNS generates a population of solutions by executing an ALNS several times. Then, the population is subject to a crossover phase, during which new individuals are created by re-applying the ALNS that utilizes information from the population. We streamline the HALNS for the capacitated VRP and the VRP with time windows. The versions implemented use specialized removal operators, a simple insertion operator, an improved crossover mechanism, and unlike the HALNS, no adaptive operator selection, leading to the description as hybrid large neighborhood search (HLNS). In the case of the CVRP, we extend the HLNS by a strong local search based on the open-source implementation of Vidal’s hybrid genetic search. The HLNS achieves competitive results on small to medium size benchmark instances, but is less effective for large-scale instances due to the lack of sparsification techniques or neighborhood limitations. Despite this shortcoming, the HLNS is a simple framework that can be easily adapted for further VRP variants.

[Challenge Paper]   [Video]

In this paper, we propose an efficient heuristic algorithm for solving the vehicle routing problem with time windows. To minimize the total distance of the route, it is necessary to try out solutions with different numbers of routes. Therefore, the algorithm mainly includes two parts, the first part minimizes the number of routes, and the second one minimizes the total length of the route under given route numbers. In the first part, our algorithm is based on ejection pool (EP) [3] and customers’ penalty [4], routes weighting is applied in repair. In the second part, our algorithm is based on EAMA [5] and the ruin method [1].

[Challenge Paper]   [Video]

: In our work, an effective refining heuristic algorithm for large-scale instances of Vehicle Routing Problems has been developed. The technique consists in a local search step entangled with restricted Set Partitioning problem optimization. Helsgaun’s LKH-3 algorithm has been used for the local search phase, with a number of acceleration techniques to improve its performance. The restricted Set Partitioning formulation is solved by means of a novel Set Partitioning heuristic inspired by the technique proposed by Caprara et al for the Set Covering problem. The resulting algorithm has been able to improve many best-known solutions for both CVRP and VRPTW instances used in the DIMACS 12th Implementation Challenge.

[Challenge Paper]   [Video]

The Vehicle Routing Problem with Time Windows is a more constrained version of the well-known Capacitated Vehicle Routing Problem which imposes constraints at the arrival time of the vehicles at each customer, in addition to the capacity constraints. As such, it is considered a harder variant of the CVRP. This paper describes a matheuristic algorithm for the VRPTW. The algorithm combines the Iterated Local Search metaheuristic with an exact method based on the set partitioning formulation for VRPs. In addition, we implemented several acceleration structures from the literature to improve its performance. Although the method has yet to be thoroughly tested and calibrated, it is promising, as our team got 5th place among all competitors in Phase 1, making it to the Phase 2.

[Challenge Paper]   [Video]

This paper addresses the Split Delivery Vehicle Routing Problem (SDVRP), a relaxation of the Capacitated Vehicle Routing Problem (CVRP) where the same customer can be served by multiple vehicles. Our approach is based on Iterated Local Search (ILS) and employs an improved perturbation mechanism and a new neighborhood structure called SD-Swap∗. By implementing a Lazy Static Move Descriptor (LSMD) mechanism, the proposed algorithm is quite efficient.

[Challenge Paper]   [Video]

This paper describes a heuristic method and a branch-and-cut algorithm for the split delivery vehicle routing problem (SDVRP). The heuristic is composed of 1) a constructive heuristic proposed by Wilck and Cavalier that provides good results for instances where customer demand is high relative to the vehicle capacity, 2) an adaptive large neighborhood search (ALNS) heuristic tailored for the SDVRP, 3) a route based model that combines routes to form a SDVRP solution. Input to the route based model can be routes from the constructive heuristic, the ALNS heuristic or it can be routes that are promising for the instance at hand. The exact method is based on a well-known two-index model that is a relaxation for the SDVRP. No-good cuts are added when an infeasible solution is detected. This approach has been used in the literature before but we improve results by separating capacity cuts with an exact algorithm and by solving the feasibility problem using a recent model proposed in the literature. In separate tests allowing more time, we show that this method performs well; we are able to prove optimality of several instances for the first time.

[Challenge Paper]   [Video]

The scientific community has worked for decades on vehicle routing problems, modeling many different real problems and designing exact and heuristic solution algorithms. Several commercial software packages to support routing decisions are available on the market as a proof of the practical relevance of this class of problems and of the impact of the research achievements. Technological developments are changing the way people move and goods are transported and stimulate research on new routing problems. Starting from the research carried out in the past, some recent trends will be presented together with future challenges.

[Video]

The split delivery vehicle routing problem is a variant of the well-known vehicle routing problem, where each customer can be visited by several vehicles. This paper presents an effective memetic algorithm for solving the problem. The algorithm features a general edge assembly crossover to generate promising offspring solutions from the perspective of assembling suitable edges and an effective local search to improve each offspring solution. The algorithm is further reinforced by a feasibility-restoring procedure, a diversification-oriented mutation and a quality-and-distance pool updating technique.

[Challenge Paper]   [Video]

In this paper, we propose a new matheuristic for solving the vehicle routing problem with split deliveries. The matheuristic constructs a starting feasible solution by splitting the demand at each customer into predefined partial demands, duplicating the customer nodes for each partial demand and solving the expanded graph as a normal capacitated vehicle routing problem. Once the initial solution is created, we run the improvement phase of the matheuristic to improve the set of routes in the initial feasible solution until the termination criterion is met. The proposed matheuristic is tested on 95 of the DIMACS instances, of which 43 of them are comparable to previously published results. On the set of comparable instances, we find a new best-known solution on 16 instances.

[Challenge Paper]   [Video]

Our solver focuses on pruning the search space associated with solving these problem instances by fixing a large fraction of the edge variables. The fixing of variables is achieved using a combination of rule-based approaches and machine learning classification models, which, in turn, are based on features derived from known heuristics, optimisation techniques and the statistical distribution of edge weights and distances of nodes from the depot and each other node. The process of reduce-and-route significantly limits the search space for a given problem so that it might be solved much more quickly than the original MILP instances, enabling us to find many new feasible solutions of the larger problem instances in the challenge and to obtain known optimal solutions for many smaller instances.

[Challenge Paper]   [Video]

To culminate the workshop and the 12th DIMACS Implementation Challenge, Eduardo Uchoa unveiled the winners of the CVRP and VRPTW tracks.

[Video]