4A1 A LOCAL SEARCH ALGORITHM FOR ROUTING AND SCHEDULING PROBLEMS WITH TIME WINDOW AND TRAVELING TIME CONSTRAINTS(Technical session 4A : Vehicle routing)

概要

論文の詳細を見る
We generalize the standard vehicle routing problem by allowing soft time window and soft traveling time constraints, and propose a local search algorithm, where both constraints are treated as cost functions. With the proposed generalization, the problem becomes very general, and can treat various scheduling problems, e.g., with earliness and tardiness costs, and flexible processing time. In our algorithm, local search is used to determine routes. After fixing the route for a vehicle, we must determine the optimal start times of processing at customers so that the total cost is minimized. This subproblem is NP-hard when cost functions are general, and can be efficiently solved with dynamic programming when traveling cost functions are convex. We then report computational results for benchmark instances, and confirm the usefulness of the proposed generalization.
一般社団法人日本機械学会の論文
2004-05-24