ロジスティクス工学 第7章 配送計画モデル 東京商船大学 久保 幹雄 ロジスティクス工学 第7章 配送計画モデル 東京商船大学 久保 幹雄
Vehicle routing problem (route-first/cluster second algorithm) 1 2 3 4 5 6 Capacity of the vehicle is 4. Each customer has a unit demand. 距離行列 0 1 5 4 5 2 3 1 0 4 5 6 2 3 5 4 0 8 9 7 7 4 5 8 0 2 4 5 5 6 9 2 0 4 4 2 2 7 4 4 0 1 3 3 7 5 4 1 0
Find a giant tour by solving the traveling salesman problem 1 2 3 4 5 6
Shortest path network Let Cij of the distance of the SP network be the cost of visiting customers i+1, i+2,...,j in the order of the given giant tour if the total demand of these customers does not exceed the capacity of the vehicle. Again, 0 is a dummy node. 0 1 2 3 4 5 6 Then, solve the shortest path problem using Dijkstra’s algorithm.