مدل‌سازي و ‌حل مسيله مسيريابي وسيله نقليه با تابع هزينه پله‌اي وابسته به مقدار بارگيري (مطالعه موردي: شركت فرگاز مازندران)

Modeling and Solving the Vehicle Routing Problem with Step Cost Function and Loading Consideration: A case study

موضوع مسيريابي وسيله نقليه، يكي از موضوعات مهم در برنامه‌ريزي حمل‌ونقل است. در اكثر پژوهش‌هاي پيشين، هدف اين موضوعات حداقل‌كردن كل مسافت طي‌شده توسط وسايل نقليه بوده‌ است. ولي در صنعت، موارد متعددي يافت مي‌شود كه مقدار محصول بارگيري‌شده جزو مولفه‌هاي تابع هزينه است. در اين مقاله ابتدا يك موضوع مسيريابي وسيله نقليه ناهمگن، مدل‌سازي شده است كه در آن هزينه پرداختي براي هر وسيله نقليه، برابر حاصل‌ضرب نرخ هزينه در مقدار بارگيري است و نرخ هزينه نيز بر اساس تابع پله‌اي بر اساس مسافت طي‌شده توسط وسيله نقليه محاسبه مي‌شود. سپس به كمك تكنيك‌هاي تحليلي، مدل غيرخطي ساخته‌‌شده با مدل خطي معادل‌سازي شده است. در ادامه، يك راه‌ حل ابتكاري سازنده براي اين موضوع پيشنهاد و كارآيي آن با حدود جواب بهينه حاصل از نرم‌افزار Cplex 12.2 سنجيده شده است. در انتها، كاربرد اين موضوع در شركت فرگاز مازندران، جمع‌بندي نتايج حاصل از اين پژوهش و پيشنهادهايي براي تحقيقات بعدي ارايه‌ شده است.

Vehicle Routing Problem (VRP) is one of the major problems in the transportation and distribution planning. In the most previous studies, the objective of VRP models was distance and vehicle related costs. However in many industrial cases along with routing distance, vehicle loading amount is a factor of cost function. In this paper, we formulate a mixed integer non-linear programming (MINLP) model for heterogeneous vehicle routing problem in which problem objective has nonlinear relation with routing distance. Then by analytical methods we reformulate the model as a mixed integer programming (MIP). In this model, at the first transportation cost rate is determined by step function. Then cost of each vehicle calculated by multiplying the transportation cost rate to its loading amount. Similar to other VRP problems proposed model is also NP-hard. We develop constructive heuristic algorithm to obtain an approximate solution for this problem. This algorithm is developed based on creating a traveling salesman problem (TSP) tour and partitioning it into vehicle routs by heuristic methods. We name proposed algorithm as Salesman Rout Partitioning for Vehicles (SRPV). In order to evaluation the effectiveness of SRPV algorithm we design 54 experiments in four scenarios. In one hand, lower and upper bounds for these experiments have been obtained by commercial optimization software Cplex 12.2. Besides, proposed heuristic are programmed and compiled using Matlab 2010. Furthermore effectiveness of SRPV algorithm is investigated by two measures, difference percentage and complexity percentage. Our findings indicate that SRPV algorithm sufficiently effective as constructive heuristic for considered type of vehicle routing problem. Moreover, to demonstrate the practicality of proposed model and solution heuristic, we study an industrial case at FERGAZ Company. This company charges gas cylinders and distributes them among geographically dispersed customers. By using Cplex 12.2 we couldn’t find any feasible solution for FERGAZ’s problem, but approximate solution could be found by heuristic algorithm.