Optimization Online


The Vehicle Routing Problem with Occasional Drivers

Claudia Archetti(claudia.archetti***at***unibs.it)
Martin Savelsbergh(martin.savelsbergh***at***isye.gatech.edu)
M. Grazia Speranza(grazia.speranza***at***unibs.it)

Abstract: We consider a setting in which a company not only has a fleet of capacitated vehicles and drivers available to make deliveries, but may also use the services of occasional drivers who are willing to make a single delivery using their own vehicle in return for a small compensation if the delivery location is not too far from their own destination. The company seeks to make all the deliveries at minimum total cost, i.e., the cost associated with its own vehicles and drivers plus the compensation paid to the occasional drivers. The option to use occasional drivers to make deliveries gives rise to a new and interesting variant of the classical capacitated vehicle routing problem. We design and implement a multi-start heuristic which produces solutions with small errors when compared with optimal solutions obtained by solving an integer programming formulation with a commercial solver. A comprehensive computational study provides valuable insight into the potential of using occasional drivers to reduce delivery costs, focusing primarily on the number and flexibility of occasional drivers and the compensation scheme employed.

Keywords: Vehicle Routing Problem, Crowdshipping, Occasional Drivers.

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

Category 2: Combinatorial Optimization (Meta Heuristics )

Category 3: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Department of Economics and Management, University of Brescia, 2015

Download: [PDF]

Entry Submitted: 01/18/2016
Entry Accepted: 01/18/2016
Entry Last Modified: 01/18/2016

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