近幾年來，國內宅配市場日趨受到重視，如何在這競爭激烈的新興宅配市場中，有效降低營運成本以維持本身競爭優勢為一重要課題。本研究主要是針對宅配業之車輛路線規劃問題進行探討，期能藉由有效的配送路線規劃，協助國內宅配業進行貨物配送作業。經實地訪查了解，此路線規劃問題之特性包括單一性、順序性、動態性、以及收送性，故本研究將此問題稱為考量回頭車利用之動態收送貨旅行銷售員問題。據此，本研究將依動態需求出現與否，分別構建先期路線規劃模式與即時路線規劃模式，但對較大型之路線規劃問題，較不易利用數學模式進行求解，故本研究將再研提一啟發法，以利於處理實務上中、大型問題。
本研究所提出之啟發式解法可分為兩部份，就未考量動態需求，依操作可分為路線構建、改善、合併、插入及兩次改善等六個步驟；而動態需求出現時，依運輸成本及服務水準之不同考量因素，提出三種求解策略。此外，本研究依問題特性，據以設計測試題目並進行求解分析，經求解結果顯示，本研究所研提求解方法除確實能有效求解中、大型問題外，面對不確定需求產生，亦能依不同決策合理反應，故進一步進行實例研究，並與現況之規劃結果進行比較分析，經求解實例之結果顯示，本研究之路線規劃結果將較現況路線之總行駛距離節省約五分之一，本研究成果應可作為後續研究與相關業者之參考。

Recently, more attention is being focused on the business of home delivery service. How to minimizing transportation costs is an important issue in this business. The research makes an attempt to study how the sale drivers find optimal routes to pick up and deliver packets each day. Essentially, this problem for each sale driver is a Traveling Salesman Problem, consisting of four aspects: single-vehicle, ordered cluster, dynamic and pickup-delivery. We define it as a Pickup-Delivery Dynamic Traveling Salesman Problem with Backhauls (PDDTSPB). In order to deal with the dynamic aspect in the PDDTSPB we formulate a pre-event routing model and a real-time routing model for it. Furthermore, heuristic algorithms are developed for these two models, respectively.
The computation results of test problems show that the heuristic algorithms can efficiently solve the PDDTSPB. Moreover, a real-world case is also tested with these heuristic algorithms. It is showed that a near-optimal route, with 20% savings from the real-world data, can be obtained. It is hoped that the heuristic algorithms can help sale drivers in the home delivery industry to solve their PDDTSPB.

1.交通部運輸研究所，台灣地區交通路網數值地圖1.0版，民國90年。
2.林志鴻，「考量回頭車利用之收送貨旅行銷售員問題」，南台科技大學行銷與流通管理系(送審中)，民國92年。
3.林沛傑，「電子商務模式下的宅配系統比較」，物流技術與戰略，第17期，頁63-70，民國89年。
4.呂英志，即時資訊下車輛路線問題之研究，逢甲大學交通工程與管理研究所碩士論文，民國91年。
5.胡大瀛、呂英志、陳仲強、陳佳貝，「動態車路線問題之研究」，中華民國運輸學會第十六屆學術論文研究會論文集，頁133-142，民國90年。
6.張美香、陳祥瑞，「含時窗限制及撿收之動態車輛途程規劃之研究」，中華民國第七屆網路運輸研討會，民國91年。
7.梅明德、謝浩明，「時窗限制動態車輛路線問題之線上型路線建立啟發式解法」，運輸學刊，第十三卷第二期，頁73-111，民國90年。
8.陳春益，物流管理課程講義，成功大學交通管理科學研究所，民國90年。
9.陳振，「風起雲湧—臺灣宅配戰國元年」，物流技術與戰略，第16期，頁62-69，民國89年。
10.陳慧娟編撰，物流中心作業系統，經濟部商業司，第一版，民國84年。
11.陳隆熙，一個解決TSP最佳解的穩定方法－以TA演算法為例，大葉大學工業工程學系碩士論文，民國91年。
12.陳建緯，大規模旅行推銷員問題之研究：鄰域搜尋法與巨集啟發式解法之應用，交通大學運輸工程與管理學系碩士論文，民國90年。
13.蘇昭銘、張志鴻，「應用GIS改良線上型車輛路線問題最近鄰點搜尋法之研究」，中華民國第七屆網路運輸研討會，民國91年。
14.蘇昭銘、張志鴻、莊子駿，「應用GIS分析宅配業車輛路線排程作業之研究」，中華民國運輸學會第十六屆論文研討會，頁411-420，民國90年。
15.Anily, S., Bramel, J. and Hertz, A., “A 5/3-approximation algorithm for the clustered traveling salesman tour and path problems,” Operations Research Letters, Vol. 24, pp.29-35, 1999.
16.Anily, S., Mosheiov, G., “The traveling salesman problem with delivery and backhauls,” Operations Research Letters, Vol. 16, pp.11-18, 1994.
17.Bell, W. J., Dalberto, L. M., Fisher, M. L., Greenfield, A. J., Jaikumar, R., Kedia, P., Mack, R. G. and Prutzman, P. J., “Improving the distribution of industrial gases with and on-line computerized routing and scheduling optimizer,” Interfaces, Vol.13, pp.4-23, 1983.
18.Benton, W. C., Rossetti, M. D., “The vehicle scheduling problem with intermittent customer demands,” Computers and Operations Research, Vol.19, pp.521-531, 1992.
19.Bertsimas, D. J., “Stochastic and dynamic vehicle routing in the euclidean plane with multiple capacitated vehicles,” Operations Research, Vol.41, pp.60-76, 1993.
20.Bertsimas, D. J., Ryzin, G. V., “A stochastic and dynamic vehicle routing problem in the euclidean plane,” Operations Research, Vol.39, pp.601-615, 1991.
21.Bodin, L., Golden, B., Assad, A. and Ball, M., “Routing and scheduling of vehicles and crews: the state of the art,” Computers and Operations Research, Vol.10, pp.63-211, 1983.
22.Brown, G. G., Graves, G. W., “Real-time dispatch of petroleum tank trucks,” Management Science, Vol.27, No.1, pp.19-32, 1981.
23.Caliper Corporation, TransCAD Reference Manual, 1990.
24.Casco, D. O., Golden, B. L. and Wasil, E. A., “Vehicle routing with backhauls: models, algorithms, and case studies,” in Vehicle Routing: Methods and Studies, eds. Golden B. L. and Assad A. A., North Holland: Amsterdam, 1988.
25.Clarke, G., Wright, J.W., “Scheduling of vehicles from a central depot to a number of delivery points,” Operations Research, Vol.12, pp.568-581, 1964.
26.CPLEX Optimization, Inc., CPLEX Manual, 1993.
27.Dror, M., “Modeling vehicle routing with uncertain demands as a stochastic program: properties of the corresponding solution,” European Journal of Operational Research, Vol.64, pp.432-441, 1993.
28.Dror, M., Levy, L., “A vehicle routing improvement algorithm comparison of a greedy and a matching implementation for inventory routing,” Computers and Operations Research, Vol.13, pp.33-45, 1986.
29.Dueck, G., Scheuer, T., “Threshold accepting: a general purpose optimization algorithm appeared superior to simulated annealing,” Journal of Computational Physics, Vol.90, pp.161-175, 1990.
30.Flood, M. M., “The Traveling Salesman Problem,” Operations Research, Vol.4, pp.61-75, 1955.
31.Gendreau, M., Hertz, A. and Laporte, G., “The traveling salesman problem with backhauls,” Computers and Operations Research, Vol.23, No.5, pp.501-508, 1996.
32.Gendreau, M., Laporte, G. and Sequin, R., “Stochastic vehicle routing,” European Journal of Operational Research, Vol.88, pp.3-12, 1996.
33.Gendreau, M., Laporte, G. and Vigo, D., “Heuristics for the traveling salesman problem with pickup and delivery,” Computers and Operations Research, Vol.26, No.7, pp.699-714, 1999.
34.Golden, B., Bodin, L. and Stewart, W., “Approximate traveling salesman algorithms,” Operations Research, Vol.26, pp.694-711, 1980.
35.Hall, R. W., “Pickup and Delivery Systems for Overnight Carriers,” Transportation Research, Vol.30A, No.3, pp.173-187, 1996.
36.Held, M., Karp, R. M., “A dynamic programming approach to sequencing problems,” Journal of Society Industrial and Applied Mathematics, Vol.10, pp.196-210, 1962.
37.Ichoua, S., Gendreau, M. and Potvin, J. Y., “Diversion issues in real-time vehicle dispatching,” Transportation Science, Vol.34, No.4, pp.426-438, 2000.
38.Jongens, K., Volgenant, T., “The symmetric clustered traveling salesman problem,” European Journal of Operational Research, pp.68-75, 1985.
39.Kalantari, B., Hill, A. V. and Arora, S. R., “An algorithm for the traveling salesman problem with pickup and delivery customers,” European Journal of Operational Research, Vol.22, pp.377-386, 1985.
40.Madsen, B. G., Ravn, H. F. and Rygaard, J. M., “A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities and multiple objectives,” Annals of Operations Research, Vol.60, pp.193-208, 1995.
41.Miroslaw, M., Mohan, G. and Mihir, P., “Serial and parallel simulated annealing and tabu search algorithms for the Traveling Salesman Problem,” Annals of Operations Research, Vol.21, pp.59-84, 1989.
42.Mosheiov, G., “The traveling salesman problem with pick-up and delivery,” European Journal of Operational Research, pp.299-310, 1994.
43.Powell, W. B., Jaillet, P. and Odoni, A., “Stochastic and dynamic networks and routing,” in Network Routing, Handbooks in Operations Research and Management Science, Vol.8, eds. Ball M. O., Magnanti T. L., Monma C. L., and Nemhauser G. L., Vol.8, North Holland: Amsterdam, 1995.
44.Powell, W., Sheffi, Y., Nickerson, K. S., Butterbaugh, K. and Atherton, S., “Maximizing profits for north american van lines truckload division:a new framework for pricing and operations,” Interfaces, Vol.18, pp.21-41, 1988.
45.Psaraftis, H. N., “An exact algorithm for the single vehicle many-to-many dial-a-ride problem with time windows,” Transportation Science, Vol.17, No.3, pp.351-357, 1983.
46.Psaraftis, H. N., “Dynamic vehicle routing problems,” in Vehicle Routing: Methods and Studies, eds. Golden B. L. and Assad A. A., North Holland: Amsterdam, 1988.
47.Psaraftis, H. N., “Dynamic vehicle routing: Status and Prospects,” Annals of Operations Research, Vol.61, pp.143-164, 1995.
48.Psaraftis, H. N., “A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem,” Transportation Science, Vol.14, pp.130-154, 1980.
49.Psaraftis, H. N., “An exact algorithm for the single vehicle many-to-many dial-a-ride problem with time windows,” Transportation Science, Vol.17, pp.351-357, 1983.
50.Regan, A. C., Mahmassani, H. S. and Jailiet, P., “Improving efficiency of commercial vehicle operations using real-time information: potential uses and assignment strategies,” Transportation Research Record, Vol.1493, pp.188-198, 1994.
51.Renaud, J., Boctor, F. F. and Ouenniche, J., “A heuristic for the pickup and delivery traveling salesman problem,” Computers and Operations Research, Vol.27, pp.905-916, 2000.
52.Savelsbergh, M. W. P., “The general pickup and delivery problem,” Transportation Science, Vol.29, No.1, pp.17-29, 1995.
53.Shen, Y., Potvin, J. Y., Rousseau, J. M. and Roy, S., “A computer assistant for vehicle dispatching with learning capabilities,” Annals of Operations Research, Vol.61, pp.189-211, 1995.
54.Slater, A., “Specification for a dynamic vehicle routing and scheduling system,” International Journal of Transport Management, Vol.1, pp.29-40, 2002.
55.Swihart, M. R., Papastavrou, J. D., “A stochastic and dynamic model for the single-vehicle pick-up and delivery problem,” European Journal of Operational Research, Vol.114, pp.447-464, 1999.
56.Thangiah, S. R., Potvin, J. Y. and Sun, T., “Heuristic approaches to vehicle routing with backhauls and time windows,” Computers and Operations Research, Vol.23, No.11, pp.1043-1057, 1996.
57.Toth, P., Vigo, D., “A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls,” European Journal of Operational Research, Vol.113, pp.528-543, 1999.
58.Toth, P., Vigo, D., “An exact algorithm for the vehicle routing problem with backhauls,” Transportation Science, Vol.31, No.4, pp.372-385, 1997.
59.Wade, A. C., Salhi, S., “An investigation into a new class of vehicle routing problem with backhauls,” Omega, Vol.30, pp.479-487, 2002.
60.Waters, C. D. J., “Vehicle scheduling problems with uncertainty and omitted customers,” Journal of the Operational Research Society, Vol.40, pp.1099-1108, 1989.
61.Yano, C., Chan, T., Richter, L., Cutler, T., Murty, K. and McGettigan, D., “Vehicle routing at quality stores,” Interfaces, Vol.17, pp.52-63, 1987.