- | ||||
|
![]()
|
An Approximation Algorithm for Vehicle Routing with Compatibility Constraints
Miao Yu (miaoyu 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 Modify/Update this entry | ||
Visitors | Authors | More about us | Links | |
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
![]() |