ダウンロード数: 29
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
mfeku_37_4_252.pdf | 566.41 kB | Adobe PDF | 見る/開く |
タイトル: | Traveling Salesman Problems with a Capacity Constraint of the Delivery Truck |
著者: | ISHII, Hiroaki IBARAKI, Toshihide MINE, Hisashi |
発行日: | 31-Dec-1975 |
出版者: | Faculty of Engineering, Kyoto University |
誌名: | Memoirs of the Faculty of Engineering, Kyoto University |
巻: | 37 |
号: | 4 |
開始ページ: | 252 |
終了ページ: | 263 |
抄録: | 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. |
URI: | http://hdl.handle.net/2433/280987 |
出現コレクション: | Vol.37 Part 4 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。