ارائه ی یک الگوریتم ژنتیک جدید برای حل مسئله ی مسیریابی چند انباره با وسایل نقلیه چند ظرفیتی
محورهای موضوعی :
مدیریت صنعتی
Hossien Afzali
1
,
Gholam Reza Einy Sarkalleh
2
,
Mojtba Khademy Nejad
3
,
Elnaz Miandoabchi
4
1 - Researcher at the institute for Trade Student and Research (ITSR)
2 - Ph.D. student of industrial management and Researcher at the institute for Trade Student and Research (ITSR)
3 - M.S in Industrial management
4 - Ph.D. in Industries and Faculty Member of the Institute for Trade Student and Research (ITSR)
تاریخ دریافت : 1396/07/13
تاریخ پذیرش : 1396/11/08
تاریخ انتشار : 1397/01/20
کلید واژه:
genetic algorithms,
الگوریتم های ژنتیک,
الگوریتم حریصانه مسیریابی,
وسایل نقلیه چند ظرفیتی,
چند انباره,
Greedy algorithm,
Multi-capacity vehicle routing,
Multi-storage,
چکیده مقاله :
امروزه مسیریابی وسایل نقلیه یکی از مسائل پرکاربردترین موضوعات و مدل ها در لجستیک و مدیریت زنجیره تامین و به تبع آن در برنامه ریزی حمل و نقل می باشد که تا کنون مقالات و پژوهش های کاربردی و آکادمیک بسیار زیادی در این زمینه انجام شده و به چاپ رسیده است در این مقاله ما به ارائه یک الگوریتم ابتکاری جدید برای حل مساله ی مسیر یابی وسایل نقلیه با ظرفیت های متفاوتی از وسایل نقلیه پرداخته شده است که هدف اساسی این مقاله تخصیص نقاط تقاضا به هر مرکز و تعیین بهترین مسیر بین نقاط تخصیص یافته به هر مرکز و همچنین تعیین بهترین وسیله حمل و نقل برای هر مرکز است و در یک مطالعه موردی این مدل مورد تحلیل و بررسی قرار گرفته است و در ادامه نتایج بدست آمده که توسط الگوریتم جدید استخراج شده است را با الگوریتم های ابتکاری مقایسه گردیده و نتایج بدست آمده نشان می دهد که این الگوریتم توانایی رقابت با الگوریتم های ابتکاری و فراابتکاری های دیگر را نیز خواهد داشت.
چکیده انگلیسی:
Vehicle routing issues are one of the most common issues in supply chain management and in transport planning. So far, there have been many published academic articles and applied research papers referred in this study. A new innovative algorithm is proposed in this investigation in order to solve the problem of routing different vehicles with different capacities. The main purpose of this paper is to allocate demand points to each center and determine the best route between the points assigned to each center, as well as determine the best means of transport. The quotes are for each center and the results obtained by the new algorithm are extracted C has been compared with the original algorithms and the results show that this algorithm will be able to compete with innovative algorithms and other interoperability.
منابع و مأخذ:
Banos, R., Ortega, J., Gil, C. (1959). Marquez, A.L & de Toro, F.A., Hybrid meta-heuristic for multi-objective vehicle routing problems with time windows ,Computers & Industrial Engineering, 2013 (65): 286-296.
Baozhen, Yao, Bin Yu, Ping Hu, Junjie, Gao. (2015). An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot Mingheng Zhang.
Bookbinder, J. H., & Reece, K. E. (1988). Vehicle routing considerations in distribution system design. European Journal of Operational Research, 37, 204–213.
Bouhafs, L., Hajjam, A., & Koukam, A. (2006). A combination of simulated annealing and ant colony system for the capacitated location-routing problem. Lecture Notes in Computer Science, 4251, 409–416.
Gerhard Hiermann, Jakob, Puchinger, Stefan Ropke & Richard F., Hartl. (2016). The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations.
HoudaDerbel, BassemJarboui, SaïdHanafi, HabibChabchoub. (2012).Genetic algorithm with iterated local search for solving a location-routing problem. Expert Systems with Applications, 39, 2865-2871
Jacobsen, S. K., & Madsen, O. B. G. (1980). A comparative study of heuristics for a two-level routing-location problem. European Journal of Operational Research, 5,378–387.
Karp, R. (1972). Reducibility among combinatorial problems.In R. Miller & J. Thatcher (Eds.), Complexity of computer computations. New York, Plenum Press, 85–104.
Laporte, G., & Nobert, Y. (1981). An exact algorithm for minimizing routing and operating costs in depot location. European Journal of Operational Research, 6(2), 224–226.
Laporte, G., Nobert, Y., & Pelletier, P. (1983).Hamiltonian location problems. European Journal of Operational Research, 12, 80–87.
Lin, C. K. Y., Chow, C. K., & Chen, A. (2002). A location-routing-loading problem for bill delivery services. Computers & Industrial Engineering, 43(1–2): 5–25.
Madsen, O. B. G. (1983). Methods for solving combined two level location routing problems of realistic dimensions. European Journal of Operational Research, 12, 295–301.
Marinakis, Y., & Marinaki, M. (2008). A particle swarm optimization algorithm with path relinking for the location routing problem. Journal of Mathematical modeling and algorithms, 7, 59–78.
Min, H., Jayaraman, V., & Srivastava, R. (1998). Combined location-routing problems: A synthesis and future research directions. European Journal of Operational Research, 108(1): 1–15.
Monirehalsadat Mahmoudi, Xuesong Zhou. (2016). Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state–space–time network representations School of Sustainable Engineering and the Built Environment, Arizona State University, Tempe, AZ 85281, USA
Nagy, G., & Salhi, S. (2007). Location-routing: Issues, models and methods. European Journal of Operational Research, 177, 649–672.
Prins, C., Prodhon, C., & Wolfler Calvo, R. (2004). Nouveaux algorithms pour le problems de localisationetroutage sous contraintes de capacité. In Proceedings of the MOSIM’, 04, (2): 1115–1122): Lavoisier, Ecole des Mines de Nantes, France.
Prins, C., Prodhon, C., & Wolfler Calvo, R. (2006). Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking. 4OR, 4(3): 221–238.
Prins, C., Prodhon, C., & Wolfler Calvo, R. (2006).A memetic algorithm with population management (MA|PM) for the capacitated location-routing problem. Lecture Notes in Computer Science, 3906, 183–194.
Prins, C., Prodhon, C., Ruiz, A., Soriano, P., &WolflerCalvo, R. (2007).Solving the capacitated location-routing problem by a cooperative Lagrangean relaxation granular tabu search heuristic. Transportation Science, 41(4), 470–483.
Salhi, S., & Rand, G. K. (1989). The effect of ignoring routes when locating depots. European Journal of Operational Research, 45, 150–156.
Tavakkoli-Moghaddam, Reza, Masoudi, Shaqayeq & Eghbali, Hamed. (2016). Solving a New Mathematical Model for a Multi-Objective and Multi-Depot Vehicle Routing Problem by a Non-dominated Sorting Genetic Algorithm,167-175
Vincent F., Yu, Shih-Wei Lin, Wenyih, Lee, & Ching-Jung Ting. (2009). A simulated annealing heuristic for the capacitated location routing problem. Computers & Industrial Engineering, 58, 288-299.
Yousefikhoshbakht1, M. & Khorram, E. (2012). Solving the vehicle routing problem by a hybrid meta-heuristic algorithm. Journal of Industrial Engineering International, 8(11): 1-9.
25. Wu, T. H., Low, C., & Bai, J. W. (2002). Heuristic solutions to multi-depot location-routing problems. Computers & Operations Research, 29(10), 1393–1415.
_||_
Banos, R., Ortega, J., Gil, C. (1959). Marquez, A.L & de Toro, F.A., Hybrid meta-heuristic for multi-objective vehicle routing problems with time windows ,Computers & Industrial Engineering, 2013 (65): 286-296.
Baozhen, Yao, Bin Yu, Ping Hu, Junjie, Gao. (2015). An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot Mingheng Zhang.
Bookbinder, J. H., & Reece, K. E. (1988). Vehicle routing considerations in distribution system design. European Journal of Operational Research, 37, 204–213.
Bouhafs, L., Hajjam, A., & Koukam, A. (2006). A combination of simulated annealing and ant colony system for the capacitated location-routing problem. Lecture Notes in Computer Science, 4251, 409–416.
Gerhard Hiermann, Jakob, Puchinger, Stefan Ropke & Richard F., Hartl. (2016). The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations.
HoudaDerbel, BassemJarboui, SaïdHanafi, HabibChabchoub. (2012).Genetic algorithm with iterated local search for solving a location-routing problem. Expert Systems with Applications, 39, 2865-2871
Jacobsen, S. K., & Madsen, O. B. G. (1980). A comparative study of heuristics for a two-level routing-location problem. European Journal of Operational Research, 5,378–387.
Karp, R. (1972). Reducibility among combinatorial problems.In R. Miller & J. Thatcher (Eds.), Complexity of computer computations. New York, Plenum Press, 85–104.
Laporte, G., & Nobert, Y. (1981). An exact algorithm for minimizing routing and operating costs in depot location. European Journal of Operational Research, 6(2), 224–226.
Laporte, G., Nobert, Y., & Pelletier, P. (1983).Hamiltonian location problems. European Journal of Operational Research, 12, 80–87.
Lin, C. K. Y., Chow, C. K., & Chen, A. (2002). A location-routing-loading problem for bill delivery services. Computers & Industrial Engineering, 43(1–2): 5–25.
Madsen, O. B. G. (1983). Methods for solving combined two level location routing problems of realistic dimensions. European Journal of Operational Research, 12, 295–301.
Marinakis, Y., & Marinaki, M. (2008). A particle swarm optimization algorithm with path relinking for the location routing problem. Journal of Mathematical modeling and algorithms, 7, 59–78.
Min, H., Jayaraman, V., & Srivastava, R. (1998). Combined location-routing problems: A synthesis and future research directions. European Journal of Operational Research, 108(1): 1–15.
Monirehalsadat Mahmoudi, Xuesong Zhou. (2016). Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state–space–time network representations School of Sustainable Engineering and the Built Environment, Arizona State University, Tempe, AZ 85281, USA
Nagy, G., & Salhi, S. (2007). Location-routing: Issues, models and methods. European Journal of Operational Research, 177, 649–672.
Prins, C., Prodhon, C., & Wolfler Calvo, R. (2004). Nouveaux algorithms pour le problems de localisationetroutage sous contraintes de capacité. In Proceedings of the MOSIM’, 04, (2): 1115–1122): Lavoisier, Ecole des Mines de Nantes, France.
Prins, C., Prodhon, C., & Wolfler Calvo, R. (2006). Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking. 4OR, 4(3): 221–238.
Prins, C., Prodhon, C., & Wolfler Calvo, R. (2006).A memetic algorithm with population management (MA|PM) for the capacitated location-routing problem. Lecture Notes in Computer Science, 3906, 183–194.
Prins, C., Prodhon, C., Ruiz, A., Soriano, P., &WolflerCalvo, R. (2007).Solving the capacitated location-routing problem by a cooperative Lagrangean relaxation granular tabu search heuristic. Transportation Science, 41(4), 470–483.
Salhi, S., & Rand, G. K. (1989). The effect of ignoring routes when locating depots. European Journal of Operational Research, 45, 150–156.
Tavakkoli-Moghaddam, Reza, Masoudi, Shaqayeq & Eghbali, Hamed. (2016). Solving a New Mathematical Model for a Multi-Objective and Multi-Depot Vehicle Routing Problem by a Non-dominated Sorting Genetic Algorithm,167-175
Vincent F., Yu, Shih-Wei Lin, Wenyih, Lee, & Ching-Jung Ting. (2009). A simulated annealing heuristic for the capacitated location routing problem. Computers & Industrial Engineering, 58, 288-299.
Yousefikhoshbakht1, M. & Khorram, E. (2012). Solving the vehicle routing problem by a hybrid meta-heuristic algorithm. Journal of Industrial Engineering International, 8(11): 1-9.
25. Wu, T. H., Low, C., & Bai, J. W. (2002). Heuristic solutions to multi-depot location-routing problems. Computers & Operations Research, 29(10), 1393–1415.
