Traveling Salesman Problems with a Capacity Constraint of the Delivery Truck

Abstract

This paper considers the following delivery route problem. A truck delivers rᵢ unit production resources to cities i＝2, 3, ···, n in some order starting from city 1, and receives wᵢ unit production wastes at cities i＝2, 3, ···n. Let cᵢj (1≤i≤n, 1≤j≤n, i≠j) be the time the delivery truck requires from city i to city j. At city i (i≠1), the production starts upon receiving the production resources and takes tᵢ (≥0) unit time until completion. Moreover, the delivery truck has the carrying capacity ⊿ and starts from city 1 with ren sources of Σ rᵢ units. At each city i, the total of remaining resources and the collected wastes can not exceed ⊿. The problem is to find a delivery route that visits each city i exactly once, and minimizes the completion time of production at all cities i＝2, 3, ···, n. This paper shows that the well known dynamic programming approach for the traveling salesman problem can be generalized to incorporate the capacity constraint.