Optimization Online


An Approximation Algorithm for Vehicle Routing with Compatibility Constraints

Miao Yu (miaoyu***at***umich.edu)
Viswanath Nagarajan (viswa***at***umich.edu)
Siqian Shen (siqian***at***umich.edu)

Abstract: We study a multiple-vehicle routing problem with a minimum makespan objective and compatibility constraints. We provide an approximation algorithm and a nearly-matching hardness of approximation result. We also provide computational results on benchmark instances with diverse sizes showing that the proposed algorithm (i) has a good empirical approximation factor, (ii) runs in a short amount of time and (iii) produces solutions comparable to the best feasible solutions found by a direct integer program formulation.

Keywords: vehicle routing, minimum makespan, approximation algorithm

Category 1: Combinatorial Optimization (Approximation Algorithms )

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


Download: [PDF]

Entry Submitted: 06/01/2018
Entry Accepted: 06/01/2018
Entry Last Modified: 10/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