Premium
Vehicle routing problems with regular objective functions on a path
Author(s) -
Yu Wei,
Liu Zhaohui
Publication year - 2014
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.21564
Subject(s) - tardiness , vehicle routing problem , minimax , mathematical optimization , scheduling (production processes) , computer science , job shop scheduling , path (computing) , routing (electronic design automation) , transportation theory , function (biology) , mathematics , operations research , computer network , evolutionary biology , biology
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. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 61: 34–43, 2014