نوع مقاله : مقاله پژوهشی

نویسندگان

1 گروه مهندسی صنایع، موسسه آموزش عالی آیندگان، تنکابن، ایران.

2 گروه مهندسی صنایع، پردیس دانشکده های فنی، دانشگاه تهران، تهران، ایران

3 گروه مهندسی صنایع، دانشگاه علم و صنعت ایران، تهران، ایران

10.22105/imos.2021.272652.1034

چکیده

هدف: ارائه یک مدل برنامه‌ریزی ریاضی که تابع هدف آن کمینه‌سازی هزینه وسایل نقلیه و بیشینه‌سازی میزان رضایت رانندگان وسایط نقلیه را از طریق بهینه‌سازی زمان سرویس‌دهی در حالت عدم قطعیت زمان‌های عبوری است.    
روش‌شناسی پژوهش:
با توجه به دنیای واقعی، میزان درآمد توزیع‌کنندگان رابطه مستقیمی با میزان کالای تحویلی به مشتریان دارد به همین دلیل، شرکت‌های توزیع در تلاش هستند علاوه بر کاهش هزینه حمل‌ونقل با افزایش میزان کالای قابل‌توزیع برای رانندگان رضایت آن‌ها را بیشینه نمایند. در این مقاله، با توجه به آن‌که زمان توزیع کالا توسط توزیع‌کنندگان با توجه به شرایط جوی، ترافیک و خرابی وسیله نقلیه و غیره به‌صورت غیرقطعی است، زمان‌های عبور وسایط نقلیه از مسیرها به‌صورت احتمالی در نظر گرفته می‌شود.
یافته‌ها: نتایج حاکی از آن است که کیفیت جواب‌های حاصل از الگوریتم تکامل تفاضلی با توجه به زمان حل محاسباتی مناسب است.
اصالت/ارزش‌افزوده علمی: توازن در میزان حمل کالا و توزیع کالا با توجه به زمان عبوری غیرقطعی سود توزیع‌کنندگان را افزایش و منجر به افزایش رضایت آن‌ها می‌شود.

کلیدواژه‌ها

عنوان مقاله [English]

Solving a Vehicle Routing Problem under Uncertainty by a Differential Evolution Algorithm

نویسندگان [English]

  • Alireza Salamatbakhsh 1
  • Reza Tavakkoli-Moghaddam 2
  • Ali Pahlevani 3

1 Department of Industrial Engineering, Ayandegan Institute of Higher Education, Tonekabon, Iran

2 Department of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

3 Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran

چکیده [English]

Purpose:In the real world, because of decreasing the related cost, the vehicles should return to the depot after serving the last customer’s location. This paper investigates the problem of the increasing service time by using the stochastic time for each tour such that the total traveling time of the vehicles is limited to a specific limit based on a defined probability.
Methodology:It is proven that classic models in vehicle routing problems (VRPs) belong to the class of NP-hard ones; thus, due to its complexity using exact methods in large-scale problems, a meta-heuristic based differential evolution (DE) algorithm.
Findings: The obtained results indicate the efficiency of the proposed DE algorithm.
Originality/Value: The total travel time is limited to a definite probability percent, and also other constraints (e.g., capacity and time distribution restrictions) are considered while the total cost of the transportation is minimized.

کلیدواژه‌ها [English]

  • vehicle routing problem
  • Differential evolution algorithm
  • Uncertainty
Chiang, W. C., & Russell, R. A. (1996). Simulated annealing metaheuristics for the vehicle routing problem with time windows. Annals of operations research, 63(1), 3-27.
Christofides, N., Mingozzi, A., & Toth, P. (1979). The vehicle routing problem. Combinatorial optimization. Chichester, Wiley, pp 315–338
Cordeau, J. F., & Maischberger, M. (2012). A parallel iterated tabu search heuristic for vehicle routing problems. Computers & operations research39(9), 2033-205.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science6(1), 80-91.
Das, S., & Suganthan, P. N. (2010). Differential evolution: a survey of the state-of-the-art. IEEE transactions on evolutionary computation15(1), 4-31.
Erera, A. L., Morales, J. C., & Savelsbergh, M. (2010). The vehicle routing problem with stochastic demand and duration constraints. Transportation science44(4), 474-492.
Goodson, J. C., Ohlmann, J. W., & Thomas, B. W. (2012). Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand. European journal of operational research217(2), 312-323.
Jozefowiez, N., Semet, F., & Talbi, E. G. (2009). An evolutionary algorithm for the vehicle routing problem with route balancing. European journal of operational research195(3), 761-769.
Kunnapapdeelert, S., & Kachitvichyanukul, V. (2015). Modified DE algorithms for solving multi-depot vehicle routing problem with multiple pickup and delivery requests. In Toward sustainable operations of supply chain and logistics systems (pp. 361-373). Springer, Cham.
Lee, T., & Ueng, J. (2001). A study of vehicle routing problems with load balancing. International journal of physical distribution and logistics management, 29, 646–658.
Lenstra, J. K., & Kan, A. R. (1981). Complexity of vehicle routing and scheduling problems. Networks11(2), 221-227.
Lin, S. W., Vincent, F. Y., & Chou, S. Y. (2009). Solving the truck and trailer routing problem based on a simulated annealing heuristic. Computers & operations research36(5), 1683-1692.
Maden, W., Eglese, R., & Black, D. (2010). Vehicle routing and scheduling with time-varying data: a case study. Journal of the operational research society61(3), 515-522.
Novoa, C., & Storer, R. (2009). An approximate dynamic programming approach for the vehicle routing problem with stochastic demands. European journal of operational research196(2), 509-515.
Qin, A. K., & Suganthan, P. N. (2005, September). Self-adaptive differential evolution algorithm for numerical optimization. In 2005 IEEE congress on evolutionary computation, (pp. 1785-1791).
Reimann, M., Stummer, M., & Doerner, K. (2002). A savings-based ant system for the vehicle routing problem. In proceedings of the 4th annual conference on genetic and evolutionary computation, (pp. 1317-1326).
Ribeiro, R., & Ramalhinho Dias Lourenço, H. (2001). A multi-objective model for a multi-period distribution management proble. SSRN electronic journal, 1, 97–102.
Storn, R., & Price, K. (1997). Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces. Journal of global optimization11(4), 341-359.
Tasan, A. S., & Gen, M. (2012). A genetic algorithm-based approach to vehicle routing problem with simultaneous pick-up and deliveries. Computers & industrial engineering62(3), 755-761.