本研究探討DTSPMS(the double traveling salesman problem with multiple stacks)。考慮收貨與送貨兩個相互獨立的路網，一組多個貨件，以及一輛貨車。每一貨件在收貨路網中各有一個取貨點，並在送貨路網中各有一個送貨點。所有貨件大小、形狀均相同。貨車上有一組若干個堆疊，於收貨路網中每收取一件貨後即置入其中一個堆疊。一個完整的收送貨作業是由收貨路網的基地點出發，完成所有的收貨任務回到該基地點後，再一次將所有貨物運至送貨路網的基地點開始派送任務。而貨件在各堆疊之置入與取出必須滿足先進後出之規則，且置入後不可調整位置。本問題的目標為求解收送貨路線總長度最小的解。
本研究由堆疊組狀態為切入點設計求解演算法。利用與堆疊組全載組態相容的最佳收送貨路線總成本作為該堆疊組之品質評估標準，由起始堆疊組開始，透過逐步改變堆疊組全載組態找尋最佳的堆疊組，並透過門檻接受法，用以判斷是否接受搜尋過程取得的新堆疊組全載組態，藉此引導演算法的求解方向。
於起始解階段中，先合併考慮兩個路網中的節線，再以最小覆蓋樹模型將客戶點分群並排序，快速的產生一組品質不錯的起始堆疊組態。求解過程分為起始解產生與搜尋求解兩個階段，而搜尋求解階段則分為深度求解與廣度搜尋兩種策略交替進行。由廣度搜尋開始，藉由變動堆疊組全載組態中貨件的位置找尋較佳的貨件排列方式。接著透過深度求解依據堆疊組狀態建構一輔助網路，以最短路徑問題求解對應該堆疊組的最佳收貨路線與送貨路線。實作過程中，透過嚴謹的資料結構設計，大幅提高深度求解之演算效率。
使用題庫及自行隨機產生問題測試結果發現本研究所提出之演算法可以大幅加速求解過程，使得能夠求解之問題規模遠大於文獻所見。然而所得解之品質未臻理想，為後續研究之重要課題。

In this work we investigate the double traveling salesman problem with multiple stacks (DTSPMS). Consider a set of items that are all identical in size and shape, and a truck equipped with a set of stacks. Each item has an origin point in a pickup network, as well as a destination point in another delivary network. Starting from one depot, the truck collects the items one by one, and stows each item in one of the stacks as soon as it is picked up. After gathering all the items, the truck returns to the depot, travels to another depot in the delivary network, and distributes the items one at a time. It returns to the second depot upon completion. No reshuffling of collected items is allowed, and each stack follows the last-in-first-out rule while delivering. The optimization goal is to minimize the total travel distance.
The neighborhood search-based heuristic is centered around the arrangement of the stack set. Starting from an initial configuration, in each iteration the heuristic adjusts the positions of a few items in the stacks, evaluates the new configuration, and accepts or rejects it according to a simple threshold accepting rule.
At the beginning, the heuristic combines the two networks, partitions the items into groups with a minimum-spanning-tree model, and generates the initial stack configuration accordingly. The heuristic performs two subroutines in each iteration. First, the diversification search subroutine exchanges the positions of the items in the stacks to search for better configurations. After that, the intensification search subroutine solves for the optimal pickup tour and the optimal delivary tour corresponding to a given stack configuration. Each of the two tours are obtained by solving a shortest-path problem in an auxiliary network, which can be performed very efficiently.
Computational testing with benchmark as well as randomly-generated problems indicate that the proposed heuristic is able to solve instances that are much larger than those seen in the literature, in shorter CPU time. However, the quality of the solutions for smaller instances are inferior, and their improvement calls for more research in the future.

[1] Ahuja, R., Magnanti, T., Orlin, J., 1988. Network flows.
[2] Carrabs, F., Cerulli, R., Cordeau, J.F., 2007. An additive branch-and-bound algorithm for the pickup and delivery traveling salesman problem with LIFO or FIFO loading. INFOR: Information Systems and Operational Research 45(4), 223-238.
[3] Carrabs, F., Laporte, G., Cordeau, J.F., Transportation, C.f.R.o., 2005. Variable neighborhood search for the pickup and delivery traveling salesman problem with LIFO loading. INFORMS JOURNAL ON COMPUTING 19, 618-632.
[4] Casazza, M., Ceselli, A., Nunkesser, M., 2009. Efficient algorithms for the double traveling salesman problem with multiple stacks, pp. 7-10.
[5] Cordeau, J.F., 2004. Transportation on demand.
[6] Cordeau, J.F., Iori, M., Laporte, G., Salazar Gonzalez, J.J., 2007. A branch and cut algorithm for the pickup and delivery traveling salesman problem with LIFO loading. Networks 55(1), 46-59.
[7] Felipe, A., Ortuno, M., Tirado, G., 2009a. The double traveling salesman problem with multiple stacks: A variable neighborhood search approach. Computers & Operations Research 36(11), 2983-2993.
[8] Felipe, A., Ortuno, M., Tirado, G., 2009b. New neighborhood structures for the Double Traveling Salesman Problem with Multiple Stacks. Top 17(1), 190-213.
[9] Felipe, A., Ortuno, M.T., Tirado, G., 2011. Using intermediate infeasible solutions to approach vehicle routing problems with precedence and loading constraints. European Journal of Operational Research 211(1), 66-75.
[10] Gendreau, M., Iori, M., Laporte, G., Martello, S., 2006. A tabu search algorithm for a routing and container loading problem. Transportation science 40(3), 342-350.
[11] Gendreau, M., Iori, M., Laporte, G., Martello, S., 2008. A Tabu search heuristic for the vehicle routing problem with two dimensional loading constraints. Networks 51(1), 4-18.
[12] Goetschalckx, M., Jacobs-Blecha, C., 1989. The vehicle routing problem with backhauls. European Journal of Operational Research 42(1), 39-51.
[13] Iori, M., Salazar-Gonzalez, J.J., Vigo, D., 2007. An exact approach for the vehicle routing problem with two-dimensional loading constraints. Transportation science 41(2), 253-264.
[14] Johnsonbaugh, R., 1997. Discrete Mathematics (Fourth edition).
[15] Kalantari, B., Hill, A.V., Arora, S.R., 1985. An algorithm for the traveling salesman problem with pickup and delivery customers. European Journal of Operational Research 22(3), 377-386.
[16] Levitin, G., Abezgaouz, R., 2003. Optimal routing of multiple-load AGV subject to LIFO loading constraints. Computers and Operations Research 30(3), 397-410.
[17] Lusby, R., Larsen, J., Ehrgott, M., Ryan, D., 2009. An exact method for the double TSP with multiple stacks. International Transactions in Operational Research 17(5), 637-652.
[18] Martin, G.E., 2001. Counting: The art of enumerative combinatorics. Springer Verlag.
[19] Parragh, S.N., Doerner, K.F., Hartl, R.F., 2008. A survey on pickup and delivery problems: Part II: Transportation between pickup and delivery locations. Journal fur Betriebswirtschaft 58(2), 81-117.
[20] Petersen, H., 2006. Heuristic solution approaches to the double TSP with multiple stacks. Centre for Traffic and Transport Kgs. Lyngby.
[21] Petersen, H., Archetti, C., Speranza, M., 2010. Exact solutions to the double travelling salesman problem with multiple stacks. Networks 56(4), 229- 243.
[22] Petersen, H., Madsen, O., 2009. The double travelling salesman problem with multiple stacks-Formulation and heuristic solution approaches. European Journal of Operational Research 198(1), 139-147.
[23] Savelsbergh, M.W.P., Sol, M., 1995. The general pickup and delivery problem. Transportation science 29(1), 17-29.
[24] Stanley, R.P., 2001. Enumerative combinatorics. Cambridge Univ Pr.
[25] Toth, P., Vigo, D., 2002a. The vehicle routing problem. SIAM, Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics.
[26] Toth, P., Vigo, D., 2002b. The vehicle routing problem. SIAM, Monographs on Discrete Mathematics and Applications.
[27] Toulouse, S., Wolfler Calvo, R., 2009. On the complexity of the multiple stack TSP, kSTSP. Theory and Applications of Models of Computation 5532, 360-369.