10:30 AM - 10:55 AM
Constructive Heuristic for a Synchronized Arc Routing Problem (SyARP)
We propose a constructive heuristic for the SyARP. It consists of determining a set of routes for snow plowing operations. All streets, some of which have multiple lanes, must be plowed by using synchronized vehicles, and the objective is to minimize the time of the longest route.
10:55 AM - 11:20 AM
A Branch-Price-and-Cut Algorithm for the Min-Max k-Vehicles Windy Rural Postman Problem
We present a branch-and-price algorithm for this arc routing problem that relies on ng-paths, three families of cutting planes and a dichotomic lower bounding procedure.
11:20 AM - 11:45 AM
Improved Lower Bounds for the Capacitated Arc Routing Problem
We present a cut-and-column generation bounding method for the CARP that is based on a set partitioning formulation, and uses a new dynamic programming method for generating elementary CARP routes. Extensive computational results show that the new bounds are tight, and permit to solve several open instances from the literature.
11:45 AM - 12:10 PM
A General Variable Neighborhood Search for the One-Commodity Pickup-and-Delivery Travelling Salesman Problem
We present Variable Neighborhood Search (VNS) approach for the one-commodity pickup-and-delivery traveling salesman problem. We adapt a collection of neighborhood structures usually used for solving classical TSP and efficiently update the data structures for feasibility checking in these neighborhoods. We improved all best-known objective values for the benchmark instances.