典型文献
A Tight Approximation Algorithm for Multi-Vehicle CVRP with Unsplittable Demands on a Line
文献摘要：
In this paper,the authors study the multi-vehicle capacitated vehicle routing problem on a line-shaped network with unsplittable demand.The objective is to find a transportation scheme to minimize the longest distance traveled by a single vehicle such that all the customers are served without violating the capacity constraint.The authors show that this problem has no polynomial-time algorithm with performance ratio less than 2 on condition that P ≠ NP,and then provide a 2-approximation algorithm.
文献关键词：
中图分类号：
作者姓名：
WU Yuanxiao;LU Xiwen
作者机构：
School of Science,East China University of Science and Technology,Shanghai 200237,China
文献出处：
引用格式：
[1]WU Yuanxiao;LU Xiwen-.A Tight Approximation Algorithm for Multi-Vehicle CVRP with Unsplittable Demands on a Line)[J].系统科学与复杂性学报（英文版）,2022(05):1902-1909
A类：
Unsplittable,capacitated,unsplittable
B类：
Tight,Approximation,Algorithm,Multi,Vehicle,CVRP,Demands,Line,In,this,paper,authors,study,multi,vehicle,routing,problem,line,shaped,network,demand,objective,find,transportation,scheme,minimize,longest,distance,traveled,by,single,such,that,all,customers,are,served,without,violating,capacity,constraint,show,has,polynomial,algorithm,performance,ratio,less,than,condition,NP,then,provide,approximation
AB值：
0.690355
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
