Modeling and solving some pickup-and-delivery routing problems
Tuesday 2 November 2010 at 12.30 PM by jcdubacq
Séminaire AOC (J. J. Salazar)
Tuesday 2 November 2010 at 12.30 PM
Location: B311, LIPN — Duration: one hour
Le séminaire AOC recevra le 2 novembre Juan José Salazar González (Universidad de La Laguna, Tenerife).
There are many variants of vehicle routing problems were a set of commodities must be moved between different locations. In our talk we model and solve some variants. The simplest (but still complex) version is the so-called "one-commodity pickup-and-delivery Travelling Salesman Problem" (1-PDTSP).
In this version we assume to have a single capacitated vehicle that must move one product (e.g. bicycles) between different points (customers) of a region. Each customer has a demand of the product that may be positive (delivery point) or negative (pickup point). One customer is considered to be the main office (depot) with a demand to equilibrate pickups and deliveries.
Then the 1PDTSP is the problem of finding the shortest route for the vehicle that visits each customer exactly once and satisfies the demand of all of them. We present and discuss a mathematical model, a branch-and-cut method and a metaheuristic approch for the 1-PDTSP.
Then we will discuss the multi-commodity extension of this problem, analysing first the particular cases where each commodity has only one source and one destination (called the "one-to-one m-PDTSP"). We relate this problem to others in the literature and dicuss some exact and heuristics approaches to solve it. Most of these results have been obtained while Hipólito Hernández Pérez was doing his PhD at University of La Laguna, Tenerife.