 |
 |
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.