文献类型：期刊文献

英文题名：Vehicle Routing Problems with Regular Objective Functions on a Path

作者：Yu, Wei[1];Liu, Zhaohui[1]

机构：[1]E China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China

年份：2014

卷号：61

期号：1

起止页码：34

外文期刊名：NAVAL RESEARCH LOGISTICS

收录：;EI(收录号：20140417230514);WOS:【SCI-EXPANDED(收录号:WOS:000329868300003)】；

基金：The authors thank Dr. Danny Z. Chen and Prof. Guochuan Zhang for constructive discussions on improving the analysis of the algorithm for the multivehicle problem with a minmax objective. The authors also thank the editor and the anonymous referees for improving the presentation of this paper. This research is supported by the National Natural Science Foundation of China under grant number 11171106 and the Nature Science Foundation of Zhejiang Province (China) under grant number LQ12A01011.

语种：英文

外文关键词：vehicle routing; vehicle scheduling; regular objective; complexity

摘要：We investigate the problem of scheduling a fleet of vehicles to visit the customers located on a path to minimize some regular function of the visiting times of the customers. For the single-vehicle problem, we prove that it is pseudopolynomially solvable for any minsum objective and polynomially solvable for any minmax objective. Also, we establish the NP-hardness of minimizing the weighted number of tardy customers and the total weighted tardiness, and present polynomial algorithms for their special cases with a common due date. For the multivehicle problem involving n customers, we show that an optimal solution can be found by solving O(n(2)) or O(n) single-vehicle problems. (c) 2013 Wiley Periodicals, Inc. Naval Research Logistics 61: 34-43, 2014