Optimization Online


Exact Methods for Solving Traveling Salesman Problems with Pickup and Delivery in Real Time

Ryan J. O'Neil (roneil1***at***gmu.edu)
Karla Hoffman (khoffman***at***gmu.edu)

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

Keywords: traveling salesman problem, pickup and delivery, hybrid methods, real-time optimization, constraint programming

Category 1: Applications -- OR and Management Sciences (Transportation )

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.

Download: [PDF]

Entry Submitted: 12/11/2017
Entry Accepted: 12/11/2017
Entry Last Modified: 09/02/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society