The Traveling Salesman Problem with Pickup and Delivery (TSPPD) describes the problem of finding a minimum cost path in which pickups precede their associated deliveries. The TSPPD is particularly important in the growing field of Dynamic Pickup and Delivery Problems (DPDP). These include the many-to-many Dial-A-Ride Problems (DARP) of companies such as Uber and Lyft, and meal delivery services provided by Grubhub. We examine exact methods for solving TSPPDs with consolidation in real- time applications, in which finding high quality solutions quickly is often more important that proving the optimality of such solutions. We consider enumeration, Constraint Programming (CP), Mixed Integer Programming (MIP), and hybrid methods combining CP and MIP. Our CP formulations examine multiple techniques for ensuring pickup and delivery precedence relationships. Finally, we attempt to provide guidance about which of these methods may be most appropriate for fast TSPPD solving given various time budgets.
Citation
O'Neil, Ryan J. and Hoffman, Karla. "Exact Methods for Solving Traveling Salesman Problems with Pickup and Delivery in Real Time". Technical Report. George Mason University. 4400 University Dr., Fairfax, VA. 12/2017.