Optimization Online


New Lower Bounds for the Vehicle Routing Problem with Simultaneous Pickup and Delivery

Anand Subramanian(anand***at***ic.uff.br)
Eduardo Uchoa(uchoa***at***producao.uff.br)
Luiz Satoru Ochi(satoru***at***ic.uff.br)

Abstract: This work deals with the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD). We propose undirected and directed two-commodity flow formulations, which are based on the one developed by Baldacci, Hadjiconstantinou and Mingozzi for the Capacitated Vehicle Routing Problem. These new formulations are theoretically compared with the one-commodity flow formulation proposed by Dell’Amico, Righini and Salani. The three formulations were tested within a branch and-cut scheme and their practical performance was measured in well-known benchmark problems. The undirected two-commodity flow formulation obtained consistently better results. We also ran the three formulations in a particular case of the VRPSPD, namely the Vehicle Routing Problem with Mixed Pickup and Delivery (VRPMPD). Several optimal solutions to open problems with up to 100 customers and new improved lower bounds for instances with up to 200 customers were found.

Keywords: Vehicle Routing, Simultaneous Pickup and Delivery, Commodity Flow Formulations

Category 1: Applications -- OR and Management Sciences (Production and Logistics )

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

Category 3: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: Technical Report - RT 01/10, Universidade Federal Fluminense, Niterói-RJ, Brazil, March/2010.

Download: [PDF]

Entry Submitted: 03/18/2010
Entry Accepted: 03/19/2010
Entry Last Modified: 03/18/2010

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 Programming Society