Optimization Online


Decision Diagrams 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 seeks a minimum cost path with pickups preceding deliveries. It is important in on-demand last-mile logistics, such as ride sharing and meal delivery. We examine the use of low-width Decision Diagrams in a branch-and-bound with and without Assignment Problem inference duals as a primal heuristic for finding good solutions within strict time budgets. We show these diagrams can be more effective than similarly structured hybrid Constraint Programming techniques for real-time decision making.

Keywords: traveling salesman problem pickup and delivery; decision diagrams; heuristics; real-time optimization

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


Download: [PDF]

Entry Submitted: 10/09/2018
Entry Accepted: 10/09/2018
Entry Last Modified: 03/17/2019

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