物流局是印尼政府成立的公司，負責管理糧食的分配以及糧食價格的控制。針對印尼東爪哇Nganjuk地區的物流局的運作情形，本研究提出一個有時間窗的車輛途程問題。以混合整數規劃以及基因演算法，解決糧米從中央物流局運到各倉庫、各行政區再到各村庄的運輸規劃問題。同時利用班德氏分解法於基因演算法，達成最小化運輸成本、準時配送，以及充分運用車隊產能的目標。本研究同時比較VRPTW、VRPTW with BD、naive GA以及GA-BD等方法來找出對本問題最有效率的演算法。最佳的路徑會被應用在網路地理資訊系統，提供給印尼物流局作為糧米運送決策的參考。

The Bureau of Logistics (Indonesian: Badan Urusan Logistik/BULOG) is a government-owned company in Indonesia which deals with food distribution and price control. This study addresses a vehicle routing problem with time windows encountered by BULOG in the Nganjuk district of East Java, Indonesia. A mixed-integer programming model and corresponding genetic algorithm (GA) is proposed to resolve the delivery plan of rice from a central BULOG through warehouses and sub-districts to poor villages in Nganjuk. The proposed GA is empowered by Bender decomposition (BD) as a solver to minimize the total cost of distribution, while remains timely delivery and fulfills the vehicle fleet capacity. An exact VRPTW permutation, VRPTW with BD, naive GA and a GA-BD, are used as the benchmarks to compare the efficiency of our proposed algorithm. The best route is presented in Web-GIS to facilitate BULOG’s decision as planning their rice distribution.

Aronoff S. (1989) Geographic Information System : A Management Perpective, WDL Publications, Ottawa, Canada.
Baker B. M., Sheasby J. E. (1999) Extensions to the generalised assignment heuristic for vehicle routing. European Journal of Operational Research, 119:147–57.
Benders J. F. (1962) Partitioning Procedures for Solving Mixed-Variables Programming Problems, Numerische Mathematik, Vol. 4, pp. 238-252.
Bent R., Van Hentenryck P. (2001) A two-stage hybrid local search for the vehicle routing problem with time windows, Technical report CS-01-06, Brown University.
Berbeglia G., Cordeau J.F., Gribkovskaia I., Laporte G. (2007) Static pickup and delivery problems: a classification scheme and survey, Journal Spanish Social Statistics Operation Research. 15 -1 31.
Berbeglia G., Cordeau J.F., Gribkovskaia I., Laporte G. (2007) Static pickup and delivery problems: a classification scheme and survey, J. Spanish Soc. Statistics Operation Research. 15 - 1 31.
Cakir O. (2009) Benders decomposition applied to multi-commodity, multi-mode distribution planning, Expert Systems with Applications, Vol. 36, pp. 8212-8217.
Chabrier, Alain. (2005) Vehicle routing problem with elementary shortest path based column generation. Computer & Operation Research, Vol 33, pp. 2972-2990.
Chu P. C., Beasley J. E. (1997) Agenetic algorithm for the generalised assignment problem. Computers & Operations Research, 24:17–23.
Clark G., Wright J.V. (1964) Scheduling of vehicles from a central depot to a number of delivery points, Operation Research, 12 - 568 581.
Cordeau J.-F., Soumis F., Desrosiers J. (2001) Simultaneous assignment of locomotives and cars to passenger trains, Operations research, Vol. 49, No. 4, pp. 531-548.
Cordeau J.F., Laporte G., Mercier A. (2001) A unified tabu search heuristic for vehicle routing problemswith timewindows. Journal of the Operational Research Society, 52:928–36.
Cordeau J.-F.; Soumis F., Desrosiers J. (2000). A Benders decomposition approach for the locomotive and car assignment problem. Transportation science, Vol. 34, No. 2, pp. 133-149.
Cortinhal M. J., Captivo M. E. (2003) Upper and lower bounds for the single source capacitated location problem, European journal of operational research, Vol. 151, No. 2, pp. 333-351.
Dantzig G.B., Ramser J.H. (1959) The truck dispatching problem, Management Science, 6-80 91.
De Backer B., FurnonV., Shaw P., Kilby P.h., Prosser, P. (2000) Solving vehicle routing problems using constraint programming and meta-heuristics. Journal of Heuristics, 6:501–23.
Delmaire H., Di’az J. A., Ferna’ndez E. (1999) Reactive GRASP and tabu search based heuristics for the single source capacitated plant location problem, INFOR, Canadian Journal of Operational Research and Information Processing, Vol. 37, pp. 194-225.
Roques F. A., Newbery D. M., Nuttall W. J. (2008) Fuel Mix Diversification Incentives in Liberalized Electricity Markets: A Mean–Variance Portfolio Theory Approach, Energy Economics.
Fischetti M., Salvagnin D., Zanette A. (2011) Minimal Infeasible Subsystems and Benders Cuts. DEI, University of Padova (submitted to Mathematical Programming), <http://www.dei.unipd.it/~fisch/papers/Benders.pdf> (accessed 25.10.08.).
Fisher M. L., Jaikumar R. (1981) A generalized assignment heuristic for vehicle routing. Networks, 11:109–24.
Gambardella L.M., Taillard E., Agazzi G. (1999) MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. In: Corne D, Dorigo M, Glover F, editors. New ideas in optimization. London: McGraw-Hill, .p. 63–76.
Gendreau M., Laporte G., Potvin J.Y. (2002) Metaheuristics for the capacitated VRP, In: The vehicle routing problem, SIAM monographs on discrete mathematics and applications, Philadelphia, PA: SIAM Publishing, p. 129–54.
Geoffrion A. M., Graves G.W. (1974) Multicommodity distribution system design by Benders decomposition, Management science, Vol. 20, No. 5, pp. 822-844.
Geoffrion A. M., Graves G.W. (1974) Multicommodity distribution system design by Benders decomposition, Management science, Vol. 20, No. 5, pp. 822-844.
Gillet B. E., Miller L. R. (1974) A heuristic algorithm for the vehicle dispatching problem. Journal of Operations Research, 22, 340–349.
Grefenstette J. (1995) Genetic algorithm for the traveling salesman problem, Proceedings of International Conference of Genetic Algorithm and Their Applications, 160–165.
He S., Chaudhry S., Chaudhry P. (2003) Solving a class of facility location problems using genetic algorithms, Expert Systems, Vol. 20, No. 2, pp. 86-91.
Heragu S. S., Chen J. (1998) Optimal solution of cellular manufacturing system design: Benders’ decomposition approach, European journal of operational research, Vol. 107, pp. 175-192.
Hoff A., Gribkovskaia I., Laporte G., Lokketangen., Lasso, A. (2007) solution strategies for the vehicle routing problem with pickups and deliveries, European Journal. Operation Research. 192 (3) 755 766.
Holland J. H. (1992) Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, A Bradford Book, ISBN 978-0262581110, Cambridge, MA, USA.
Holmberg K., Ling J. (1997). A Lagrangean heuristic for the facility location problem with staircase costs, European journal of operational research, Vol. 97, No. 1, pp. 63-74.
Homberger J., Gehring H. (1999) Two evolutionary meta-heuristics for the vehicle routing problem with time windows, Journal Informatics, 37:297–318.
Hwang H. S. (2002) Design of supply-chain logistics system considering service level, International journal of Computers and Industrial Engineering, 43, 283–297.
Kennington J. L., Whitler J. E. (1999) An efficient decomposition algorithm to optimize spare capacity in a telecommunications network, INFORMS Journal on computing, Vol. 11, No. 2, pp. 149-160.
Kilby Ph., Prosser P., Shaw P. (2000) A comparison of traditional and constraint-based heuristicmethods on vehicle routing problems with side constraints. Constraints;5(4):389–414.
Kim H., Sohn H., Bricker D.L. (2011) Generation expansion planning using Benders’ decomposition and generalized networks, International Journal of Industrial Engineering, Vol. 18, No. 1, pp. 25-39.
Kratica J., Tosic D., Filipovic V. Ljubic I. (2001) Solving the simple plant location problem by genetic algorithm, RAIRO Operations Research, Vol. 35, pp. 127-142.
Larra˜naga P., Kuijpers C. M. H., Murga R. H., Inza I., Dizdarevic S.(1999) Genetic algorithms for the Traveling Salesman Problem: A review of representations and operators, Artificial Intelligence Review, 13:129–170.
Lenstra J. K., Rinnooy-Kan, A.H.G. (1981) Complexity of vehicle and scheduling problems Networks, Operation Research, 11 (2) - 221 227.
Liepins G. E., Hilliard M. R. (1989) Genetic algorithms: foundations and applications, Annals of operations research, Vol. 21, pp. 31-58.
Macro D., Luca M. (1997) A cooperative learning approach to the traveling salesman problem, Libre de Bruxelles University.
Mark H. N. (1997) The Traveling Salesman Problem a Review of Theory and Current Research, Working Paper, 1–26.
Nieminen K., Ruuth S., Maros I., (2003) Genetic algorithm for finding a good first integer solution for MILP. Department of Computing, Imperial College, Department Technical Reports, 2003/4.http://www.doc.ic.ac.uk/research/technicalreports/2003/DTR03-4.pdf>, (accessed 25.10.08.).
Parragh S. N., Doerner K.F., Hartl R.F. (2008) A survey on pickup and delivery problems. Part I: transportation between customers and depot, Journal four Betriebs-wirtschaft, 58(1):21–51.
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 four Betriebswirtschaft, 58(2):81–117.
Pisinger D., Ropke S. (2007) A general heuristic for vehicle routing problems, Computers & Operations Research, 34(8):2403–35. 0305-0548.
Puchinger J., Raidl G.R. (2005) Combining metaheuristics and exact algorithms in combinatorial optimization: a survey and classification, In: First International Work-Conference on the Interplay Between Natural and Artificial Computation, Lecture Notes in Computer Science, vol. 3562. Springer, pp. 41–53.
Raidl G. R., Puchinger J. (2008) Combining (integer) linear programming techniques and metaheuristics for combinatorial optimization. In: Blum, C., Blesa Aguilera, M.J., Roli,A., Sampels, M. (Eds.), Hybrid Metaheuristics, An Emerging Approach to Optimization. Series: Studies in Computational Intelligence, vol. 114, pp. 31–62.
Randazzo C., Luna H., Mahey P. (2001) Benders decomposition for local access network design with two technologies, Discrete mathematics and theoretical computer science, Vol. 4, pp. 235-246.
Reeves C. R. (1993) Modern heuristic techniques for combinatorial problems, Oxford: Blackwell Scientific Press.
Rei W., Gendreau M., Cordeau J.-F., Soriano, P., (2006) Accelerating Benders decomposition by local branching, INFORMS Journal on Computing, in press. doi:10.1287/ijoc.1080.0296.
RochatY., Taillard E., (1995) Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics, 1:147–67.
Rolland E., Schilling D. A., Current J. R. (1996) An efficient tabu search procedure for the p-median problem, European Journal of Operational Research, Vol. 96, pp. 329-342.
Rousseau L.M., Gendrau M., Pesant G. (1999)Using constraint-based operators in a variable neighborhood search framework to solve the vehicle routing problem with time windows, CP-AI-OR.
Shaw P. (1998) Using constraint programming and local search methods to solve vehicle routing problems, Principles and practice of constraint programming, p. 417–31.
Sirikum J., Techanitisawad A., Kachitvichyanukul V.(2007) New Efficient GA-Benders’ Decomposition Method: For Power Generation Expansion Planning with Emission Controls, IEEE Transactions on Power Systems, vol. 22, no. 3, August
Sorensen K., Sevaux M. (2006). MA|PM: Memetic algorithms with population management. Computers & Operations Research, 33, 1214-1225.
Star J., Etes J. (1990) Geography Information System : An Introduction, Prentice-Hall, Inc.,Engglewood Cliffs, New Jersey.
Toth P., Vigo D. (1999) A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls, European Journal Operation Research, 113 - 528 543.
Toth P., Vigo D., (2002) The vehicle routing problem, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia.
Uno T., Hanaoka S., Sakawa M. (2005) An application of genetic algorithm for multidimensional competitive facility location problem, Proceedings of IEEE International Conference on Systems, Man and Cybernetics, pp. 3276-3280, ISBN 0-7803-9298-1, Big Island, Hawaii, USA, October 12, 2005.
Van Roy T. J. (1986) A cross decomposition algorithm for capacitated facility location, Operations Research, Vol. 34, pp. 145-163.
Van Roy, T. J., Erlenkotter D. (1982) Dual-based procedure for dynamic facility location, Management Science, Vol. 28, pp. 1091-1105.
Z. Michalewicz, (1996) Genetic Algorithms+Data Structures=Evolution Programs, 3rd ed., Springer-Verlag, Berlin Heidelberg New York.