Journées de l'optimisation 2016
HEC Montréal, Québec, Canada, 2 — 4 mai 2016
MB10 Vehicle Routing II
2 mai 2016 15h30 – 17h10
Salle: TD Assurance Meloche Monnex
Présidée par Juan Jose Salazar Gonzalez
4 présentations

15h30  15h55
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.

15h55  16h20
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.

16h20  16h45
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.

16h45  17h10
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