首站-论文投稿智能助手
典型文献
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
相似文献
机标中图分类号,由域田数据科技根据网络公开资料自动分析生成,仅供学习研究参考。