2016 Optimization Days
HEC Montréal, Québec, Canada, May 2 — 4, 2016
MB10 Vehicle Routing II
May 2, 2016 03:30 PM – 05:10 PM
Location: TD Assurance Meloche Monnex
Chaired by Juan Jose Salazar Gonzalez
4 Presentations

03:30 PM  03:55 PM
A GVNS heuristic for the traveling salesman problem with time windows  minimizing completion time
We use a GVNS (General Variable neighborhood search) heuristic for the traveling salesman problem with time windows where the objective is to minimize the completion time. We use efficient methods for checking the feasibility and the profitability of a movement, and for exploring the neighborhoods. The results indicate that our method is very competitive with the stateoftheart.

03:55 PM  04:20 PM
Undirected multidepot rural postman problem
This work studies an extension of Rural Postman Problem, where there are several depots, instead of one, from which route must be satisfy the demand, located at the edges of an undirected graph. Optimality conditions of solutions are studied, two linear integer formulations are proposed and some results are presented.

04:20 PM  04:45 PM
Goods distribution with electric vehicles: Integrating battery behaviour into routing
We introduce an electric vehicle routing problem in which a fleet of battery electric vehicles must deliver goods to a set of customers over the course of a week. The charging schedule at the depot must be determined such as to allow vehicles to complete their routes, and the battery is modeled as an equivalent electrical circuit. The objective is to minimize the sum of all energy and routing costs over the planning horizon.

04:45 PM  05:10 PM
Stronger multicommodity flow formulations of the (capacitated) sequential ordering problem
The sequential ordering problem (SOP) is the generalisation of the asymmetric travelling salesman problem in which there are precedence relations between pairs of nodes. Hernandez & Salazar introduced a multicommodity flow (MCF) formulation for a generalisation of the SOP in which the vehicle has a limited capacity. We strengthen this MCF formulation by fixing variables and adding valid equations. We then use polyhedral projection, together with some known results on flows, cuts and metrics, to derive new families of strong valid inequalities for both problems. Finally, we give computational results, which show that our findings yield good lower bounds in practice. This talk is based on a recent publication in EJOR (2016) doi:10.1016/j.ejor.2015.11.001