OPTIMIZING THE SCHEDULE FOR A FIXED VEHICLE PATH WITH CONVEX INCONVENIENCE COSTS. TECHNICAL NOTE
研究了沿固定路径的车辆调度问题，目标是最小化由凸函数建模的服务时间不便成本，并受时间窗约束。算法复杂度与节点数相关，适用于车辆路径问题的子问题求解。
This paper addresses the problem of vehicle scheduling to minimize total inconveniences for travel along a fixed path, where service times at nodes are constrained by time windows and where inconvenience is modeled using convex functions of the service times. This problem is often found as the final step or as sub-problem in most of the existing solution approaches for vehicle routing and scheduling problems. The presented algorithm's complexity in the number of unidimensional minimizations is on the order of the number of nodes for convex inconvenience functions, and the complexity is counted in number of elementary operations for quadratic and linear inconvenience functions. Also included are extensions to the case where linear costs are applied to waiting time and the case where the service time variables are discrete.