Journées de l'optimisation 2014

                             Incluant une Journée industrielle de l'optimisation

                                              HEC Montréal, 5 - 7 mai 2014


HEC Montréal, 5 — 7 mai 2014

Horaire Auteurs Mon horaire

TA1 Séance plénière 3 / Plenary Session 3

6 mai 2014 09h00 – 10h00

Salle: Amphithéâtre Banque Nationale

Présidée par Angel Ruiz

1 présentation

  • 09h00 - 10h00

    Order-First Route-Second Methods in Vehicle Routing

    • Christian Prins, prés., Université de Technologie de Troyes

    Cluster-first route-second methods like the sweep heuristic (Gillett and Miller, 1974) are well known in vehicle routing. They determine clusters of customers compatible with vehicle capacity and solve a traveling salesman problem for each cluster. The opposite approach, called route-first cluster-second, builds a TSP tour (also called giant tour) covering all customers and splits it into feasible trips. Cited as a curiosity for a long time but lacking numerical evaluation, this technique has led to successful solution methods for various vehicle routing problems in the last decade. As most implementations order the visits to customers instead of building a giant tour, such algorithms are better called order-first split-second methods. The talk will present the principles of these approaches and examples of applications, from simple cases to less obvious contexts.