Monday 19th December 2005, 11.30am
Room M128, Mathematics department, Brunel University, Uxbridge UB8 3PH
http://www.brunel.ac.uk/about/where/ux/uxacc/
Models and a Branch-and-Cut Algorithm for Pickup and Delivery Problems with
Time Windows
by
Gilbert Laporte
Canada Research Chair in Distribution Management
Centre de recherche sur les transports
Universite de Montreal
http://www.hec.ca/en/profs/gilbert.laporte.html
In the pickup and delivery problem with time windows (PDPTW), capacitated
vehicles must be routed to satisfy a set of transportation requests between
given origins and destinations. In addition to capacity and time window
constraints, vehicle routes must also satisfy pairing and precedence
constraints on pickups and deliveries. We introduce two new formulations
for the PDPTW and for the closely related dial-a-ride problem (DARP) in
which a limit is imposed on the elapsed time between the pickup and the
delivery of a request. Several families of valid inequalities are
introduced to strengthen the two formulations. These inequalities were
embedded within a branch-and-cut algorithm which was applied to optimally
solve several PDPTW and DARP instances containing up to eight vehicles and
96 requests (192 nodes).This research project was carried out with Jean-
Francois Cordeau and Stefan Ropke.
|