車輛排程問題（Vehicle Routing Problem，VRP）為許多重要系統營運的核心問題。應用於運輸系統時，此一最佳化模式容納了許多重要的考慮因素，包括時間窗的限制、可用車輛數、所服務客戶的地理位置等。眾多的考慮因素豐富了車輛排程問題的內涵，同時也增加了此一問題在學理及應用上的複雜性。
本論文探討時間窗車輛排程問題（Vehicle Routing Problem with Time Windows, VRPTW）的影響因子。研究中測試可用車輛數、車輛容量、客戶點地理位置分佈、客戶需求量、時間窗寬度、時間窗位置與地理位置分佈之相關性等六項因素之864種不同組合。求解時使用軟式時間窗限制，以先分群再排路線的求解策略產生起始可行解，再以交換客戶點的方式反覆搜尋較佳的可行解。
測試時每種參數組合分別以不同的亂數種子求解10次，以比較各種影響因子對使用的車輛數、車隊行駛總距離、車隊總服務時間、遲到的客戶點數、及早到的客戶點數的影響。測試結果顯示時間窗位置與地理位置分佈之相關性對VRPTW求解結果之影響力最為顯著。

The vehicle routing problem（VRP）sits at the core of many important system operation problems. When applied to transportation systems, this optimization model naturally incorporates a number of important factors, including time window constraints, fleet size limit, and geographical distribution of customers. These factors enriched the content of VRP, and complicated the problem in both application and theoretical aspects.
This research concerns affecting factors of the VRP with time windows, or VRPTW. We tested a total of 864 different combinations of fleet size, vehicle capacity, customer location, customer demand, width/location of time windows, and customer position-time window location correlation. The solution algorithm uses soft time window constraints. After generating the initial solution, the algorithm improves through the iterations by exchanging customers between vehicle tours.
Each of the combinations are solved 10 times under different random number seeds to derive the affects of the factors on the number of vehicles used, total driving distance, total service time, number of late services, and number of early services. The results suggest that the correlation between customer position and their time window locations has the strongest influence.

1.Achuthan, N.R., Caccetta, L., Hill, S.P., A new subtour elimination constraint for the vehicle routing problem, European Journal of Operational Research Vol. 91, No. 3, pp.573-586 (1996).
2.Alba, E., Dorronsoro, B., Computing nine new best-so-far solutions for Capacitated VRP with a cellular Genetic Algorithm, Information Processing Letters Vol. 98, pp.225-230 (2006).
3.Angelelli, E., Speranza, M. G., The periodic vehicle routing problem with intermediate facilities, European Journal of Operational Research Vol. 137, No. 2, pp. 233-247 (2002).
4.Bard, J. F., Huang, L., Dror, M., Jaillet, P., A Branch and Cut Algorithm for the VRP with Satellite Facilities, IIE Transactions 30, pp. 821-834 (1998).
5.Bodin, L., Golden, B. L., Assad, A., Ball, M., Routing and Scheduling of Vehicles and Crews, Computers & Ops Res. Vol. 10, No.2, pp.63-211 (1983).
6.Breedam, A. V., An Analysis of the Behavior of Heuristics for the Vehicle Routing Problem for a Selection of Problems with Vehicle-Related. Customer-Related, and Time-Related Constraints, Ph.D. thesis, University of Antwerp, RUCA, Belgium (1994).
7.Calvete, H. I., Galé, C., Oliveros, M.J., A goal programming approach to vehicle routing problems with soft time wimodws, European Journal of Operational Research Vol. 177, No. 3, pp.1720-1733 (2007).
8.Chapleau, L., Ferland, J.A., Rousseau, J.M., Clustering for routing in densely populated areas, European Journal of Operational Research Vol. 20, pp.48-57 (1985).
9.Christofides, N., Mingozzi, A., Toth, P. The vehicle routing problem, In Combinatorial Optimization, pp. 315-338. (1979).
10.Dror, M., Laporte, G., Trudeau, P., Vehicle routing with split deliveries, Discrete Applied Mathematics Vol. 50, No. 3 , pp.239-254 (1994) .
11.Drummond, L. M. A.., Ochi, L. S., Vianna, D. S., An asynchronous parallel metaheuristic for the period vehicle routing problem, Future Generation Computer Systems Vol. 17, No. 4, pp.379-386 (2001) .
12.Francis, P., Smilowitz, K., Modeling techniques for periodic vehicle routing problems, Transportation Research Part B: Methodological Vol. 40, No. 10, pp.872-884 (2006) .
13.Gillett, B. E., Miller, L. R., A heuristic algorithm for the vehicle dispatch problem, Operations Research 22, pp.340-349 (1974) .
14.Hsu, C.I., Hung, S.F., Li, H.C., Vehicle routing problem with time-windows for perishable food delivery, Journal of Food Engineering Vol. 80, pp.465-475 (2007).
15.Jin, M., Liu, K., Bowden, R. O., A two-stage algorithm with valid inequalities for the split delivery vehicle routing problem, International Journal of Production Economics Vol. 105, No. 1, pp. 228-242 (2007) .
16.Katoh, N., Yano, T., An approximation algorithm for the pickup and delivery vehicle routing problem on trees, Discrete Applied Mathematics Vol. 154, No. 16, pp.2335-2349 (2006) .
17.Kazaz, B., Altınkemer, K., Optimization of multi-feeder (depot) printed circuit board manufacturing with error guarantees, European Journal of Operational Research Vol. 150, No. 2, pp.370-394 (2003) .
18.Liu, F.F.H., Shen., S.Y., An overview of a heuristic for vehicle routing problem with time windows, Computers & Industrial Engineering Vol. 37, No. 1-2, pp.331-334 (1999).
19.Nagy, G., Salhi, S., Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries, European Journal of Operational Research Vol. 162, No. 1, pp.126-141(2005).
20.Nygard, K.E., Juell, P., Kadaba, N., Neural networks for selecting vehicle routing heuristics, ORSA Journal of Computing Vol. 2, No. 4, pp.353-364 (1990).
21.Oppen, J., Løkketangen, A., Arc routing in a node routing environment, Computers & Operations Research Vol. 33, No. 4, pp.1033-1055 (2006).
22.Potvin, J.Y., Robillard, C., Clustering for vehicle routing with a competitive neural network, Neurocomputing Vol. 8, pp.125-139 (1995).
23.Solomon, M. M., Algorithms for The Vehicle Routing and Scheduling Problems with Time Window Constraints, Operation Reachearch Vol.35, No.2, pp. 254-265 (1987).
24.Taillard, E., Benchmarks for basic scheduling problems, European Journal of Operational Research, Vol. 64,No. 2, pp. 278-285 (1993).
25.Thangiah, S.R., Potvin, J.Y., Sun, T., Heuristic approaches to vehicle routing with backhauls and time windows, Computers Ops Res. Vol. 23, No. 11, pp.1043-1057 (1996).
26.Tuzun, D., Magent, M.A., Burke, L.I., Selection of Vehicle Routing Heuristic Using Neural Networks, International Transactions in Operational Research Vol. 4, No.3, pp211-221 (1997).
27.李佳蓮，「車輛排程問題的廣域搜尋解法」，國立成功大學土木工程學系碩士論文（2006）
28.李宗儒、翁基華，「具工作負荷平衡之配送車輛途程問題研究」，運輸學刊，第11卷，第1期，頁59-72（1999）
29.林依潔，「整合模糊理論與螞蟻演算法於含時窗限制之車輛途程問題」，國立台北科技大學生產系統工程與管理研究所碩士論文（2003）
30.林惠民，「具時窗之多趟次車輛途程問題」，私立元智大學資訊管理學系碩士論文（2002）
31.郭晴龍，「宅配運輸途程問題之研究」，國防大學國防管理學院碩士論文（2005）
32.簡世釗，「時間窗與容量限制下車輛途程問題之研究」，國立成功大學工業管理學系碩士論文（2000）
33.謝浩明、劉金維，「時間相依暨服務時窗限制下旅行推銷員問題研究」，運輸學刊，第12卷，第1期，頁51-64（2000）
34.薛哲夫，「車輛途程規劃暨生產配送整合課題探討」，國立中央大學土木工程學系博士論文（2005）
35.http://neo.lcc.uma.es/radi-aeb/WebVRP/
36.http://neo.lcc.uma.es/radi-aeb/WebVRP/Problem_Instances/
37.http://osiris.tuwien.ac.at/~wgarn/VehicleRouting/vehicle_routing.html
38.http://web.cba.neu.edu/~msolomon/home.htm