IJE TRANSACTIONS C: Aspects Vol. 27, No. 6 (June 2014) 911-920   

downloaded Downloaded: 241   viewed Viewed: 2832

M. Setak, S. Jalili Bolhassani and H. Karimi
( Received: June 23, 2013 – Accepted in Revised Form: November 07, 2013 )

Abstract    In this paper, we study the location routing problem with replenishment facilities (LRPRF), an extension of the location routing problem (LRP) where the vehicles can replenish at some replenishment facilities. Vehicles leave the depot with load on-board, serve customers until out of load, and then either return to a replenishment facility to reload or return to the depot, completing their route. For this problem, we initiate a mathematical node-based mixed integer programming model. The objective of the problem is to find routes for vehicles to serve all the customers at a minimal cost in terms of number of routes (vehicles) and total travel cost, without violating the capacity constraint of the vehicles. The solution to the LRPRF is obtained through commercial software GAMS 23.5.1 and Genetic Algorithm (GA) in this paper. Computational results are obtained on a set of randomly generated instances and indicate the effectiveness of the proposed algorithm.


Keywords    Location Routing Problem, Replenishment Facilities, Node-based, Mixed Integer Programming, Capacity Constraint, Genetic Algorithm


چکیده    در این مقاله، مسئله مکان‌یابی- مسیریابی با تسهیلات بارگیری مجدد (LRPRF) را بررسی می‌کنیم که توسعه یافته مسئله مکان‌یابی- مسیریابی (LRP) است و در آن وسایل نقلیه می‌توانند در چند تسهیل، بارگیری مجدد انجام دهند. وسایل نقلیه با بار کامل از دپو شروع به حرکت می‌کنند، مشتریان را تا اتمام بار سرویس می‌دهند و سپس یا برای بارگیری مجدد به تسهیل بارگیری مجدد عزیمت می‌کنند یا جهت اتمام مسیرشان به دپو باز می‌گردند. برای این مسئله، یک مدل ریاضی برنامه ریزی عدد صحیح مختلط مبتنی بر گره معرفی می‌کنیم. هدف مسئله یافتن مسیر برای وسایل نقلیه جهت سرویس‌دهی به مشتریان به‌گونه‌ای است که بدون نقض کردن محدودیت ظرفیت وسایل نقلیه، تعداد مسیرها (وسایل نقلیه) و هزینه کل سفر کمینه شود. در این مقاله، مسئله LRPRF توسط نرم‌افزار GAMS 23.5.1 و الگوریتم ژنتیک حل می‌شود. نتایج محاسباتی از طریق چندین مسئله نمونه که به صورت تصادفی تولید می‌شوند بدست می‌آیند و کارائی الگوریتم پیشنهادشده را نشان می‌دهند.


1.     Sohrabi, B. and Bassiri, M., Experiments to determine the simulated annealing parameters case study in VRP”, International Journal of Engineering-Transactions B, Vol. 17, (2004), 71-80.

2.     Nagy, G. and Salhi, S., “Location-routing: Issues, models and methods”, European Journal of Operational Research, Vol. 177, (2007), 649-672.

3.     Wu, T. -H., Low, C. and Bai, J. -W., “Heuristic solutions to multi-depot location-routing problems”, Computers & Operations Research, Vol. 29, (2002), 1393-1415.

4.     Setak, M., Karimi, H. and Rastani, S., Designing incomplete hub location-routing network in urban transportation problem”, International Journal of Engineering-Transactions C: Aspects, Vol. 26, (2013), 997-1006.

5.     Tarantilis, C. D., Zachariadis, E. E. and Kiranoudis, C. T., “A hybrid guided local search for the vehicle-routing problem with intermediate replenishment facilities”, INFORMS Journal on Computing, Vol. 20, (2008), 154-168.

6.     Crevier, B., Cordeau, J. -F. and Laporte, G., “The multi-depot vehicle routing problem with inter-depot routes”, European Journal of Operational Research, Vol. 176, (2007), 756-773.

7.     Jordan, W. C. and Burns, L. D., “Truck backhauling on two terminal networks”, Transportation Research Part B: Methodological, Vol. 18, (1984), 487-503.

8.     Jordan, W. C., “Truck backhauling on networks with many terminals”, Transportation Research Part B: Methodological, Vol. 21, (1987), 183-193.

9.     Kek, A. G., Cheu, R. L. and Meng, Q., “Distance-constrained capacitated vehicle routing problems with flexible assignment of start and end depots”, Mathematical and Computer Modelling, Vol. 47, (2008), 140-152.

10.   Bard, J. F., Huang, L., Dror, M. and Jaillet. P., “A branch and cut algorithm for the VRP with satellite facilities”, IIE Transactions, Vol. 30, (1998), 821-834.

11.   Bard, J.F., Huang, L., Jaillet, P. and Dror, M., “A decomposition approach to the inventory routing problem with satellite facilities”, Transportation Science, Vol. 32, (1998), 189-203.

12.   Angelelli, E. and Speranza, G. M., “The periodic vehicle routing problem with intermediate facilities”, European Journal of Operational Research, Vol. 137, (2002), 233-247.





13.   Sevilla, F. C. and de Blas, C. S., “Vehicle routing problem with time windows and intermediate facilities”, SEIO Õ03 Edicions de la Universitat de Lleida, (2003), 3088-3096.

14.   Ghiani, G., Laganà, D., Laporte, G. and Mari, F., “Ant colony optimization for the arc routing problem with intermediate facilities under capacity and length restrictions”, Journal of Heuristics, Vol. 16, (2010), 211-233.

15.   Benjamin, A. and Beasley, J., “Metaheuristics for the waste collection vehicle routing problem with time windows, driver rest period and multiple disposal facilities”, Computers & Operations Research, Vol. 37, (2010), 2270-2280.

16.   Jie, L., Dan, L., Min, L. and Yanfeng, H., “An improved multiple ant colony system for the collection vehicle routing problems with intermediate facilities”, 8th World Congress on Intelligent Control and Automation (WCICA), IEEE, (2010), 3078-3083.

17.   Byung, K., Seongbae, K. and Surya, S., “Waste collection vehicle routing problem with time windows”, Computers & Operations Research, Vol. 33, (2006), 3624-3642.

18.   AmiriFard, F. and Setak, M., “Comparison between Two Algorithms for Multi-Depot Vehicle Routing Problem with Inventory Transfer between Depots in a Three-Echelon Supply Chain”, International Journal of Computer Applications, Vol. 28, (2011), 39-45.

19.   Hill, S.E., “Three Essays on the Location Routing Problem with Intermediate Storage Facilities”, Ph.D. Thesis, University of Alabama, (2008).

20.   Guéret, C., Heipcke, S., Prins, C. and Sevaux, M., “Applications of optimization with Xpress-MP”, Dash Optimization Ltd., United Kingdom, (2005).

21.   Derbel, H., Jarboui, B., Hanafi, S. and Chabchoub, H., “Genetic algorithm with iterated local search for solving a location-routing problem”, Expert Systems with Applications, Vol. 39, (2012), 2865-2871.

22.   Marinakis, Y. and Marinaki, M., “A bilevel genetic algorithm for a real life location routing problem”, International Journal of Logistics: Research and Applications, Vol. 11, (2008), 49-65.

23.   Cordeau, J. -F., Gendreau, M., Laporte, G., Potvin, J. -Y. and Semet, F., “A guide to vehicle routing heuristics”, Journal of the Operational Research Society, Vol. 53, (2002), 512-522.    

24.   Surekha, P. and Sumathi, S., Solution To Multi-Depot Vehicle Routing Problem Using Genetic Algorithms”, World Applied Programming, Vol. 1, (2011), 118-131.

25.   Ghiani, G., Guerriero, F., Laporte, G. and Musmanno, R., Tabu search heuristics for the arc routing problem with intermediate facilities under capacity and length restrictions, Journal of Mathematical Modelling and Algorithms, Vol. 3, (2004), 209–223.

26.   Crainic, T., Sforza, A. and Sterle, C., “Tabu Search Heuristic for a Two-echelon Location-routing Problem”, CIRRELT, (2011).

27.   Gupta, D. K., “Tabu Search for Vehicle Routing Problems (VRPs), International Journal of Computer Mathematics, Vol. 79, (2002), 693-701.

28.   Khanh, P. N., Crainic, T. G. and Toulouse. M., “A Tabu Search for Time-dependent Multi-zone Multi-trip Vehicle Routing Problem with Time Windows”, European Journal of Operational Research, (2013).

29.   Berbotto, L., García, S. and Nogales, F. J., “A Randomized Granular Tabu Search heuristic for the split delivery vehicle routing problem”, Annals of Operations Research, (2013), 1-21.

International Journal of Engineering
E-mail: office@ije.ir
Web Site: http://www.ije.ir