An Approximation Algorithm for Vehicle Routing with Compatibility Constraints

Miao Yu (miaoyuumich.edu)
Viswanath Nagarajan (viswaumich.edu)
Siqian Shen (siqianumich.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 )

Citation:

Download: [PDF]

Entry Submitted: 06/01/2018
Entry Accepted: 06/01/2018
Entry Last Modified: 10/02/2018

Modify/Update this entry