Document Type : Research Paper


1 Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran

2 Assistant Professor, Islamic Azad University, Qazvin Branch, Department of Industrial Engineering, Qazvin, Iran

3 Assistant Professor, Islamic Azad University, Qazvin Branch, Department of Industrial Engineering, Qazvin, Ira


In this paper, we study a novel pickup and delivery problem called carrier collaboration (CC). This problem includes a set of heterogenous (refrigerated and general type) vehicles with specific capacities for serving perishable products to several pickup and delivery nodes. Each carrier can have reserved and selective requests which can be delivered before the products are corrupted. The fleet of vehicles must serve reserved requests, but the selective requests can be served or not. Products are corrupted at a constant rate and a rate of corrosion in general type vehicles is greater than referigrated type veicles and the cost of using general one is less than referegireted. For the mentioned features, we develop a nonlinear mathematical model. The purpose is to find routes to maximize profits and reduce costs while at the same time, enhance customer satisfaction which is dependent on the freshness of delivered products. A Gnetic Algorithm (GA) is proposed to solve this problem due to its NP-hard nature. In this study, Variable Neighborhood Search (VNS) method is developed for improving the quality of initial solutions. Several instances are generated at different scales to evaluate the algorithm performance by comparing the results of an exact optimal solution wih that of the proposed algorithm. The obtained results demonstrate the efficiency of the proposed algorithm in providing reasonable solutions within an acceptable computational time.


Main Subjects

 Barkaoui, M., Berger, J., & Boukhtouta, A. (2015). Customer satisfaction in dynamic vehicle routing problem with time windows. Applied Soft Computing, 35, 423-432.
Bell, J. E., & McMullen, P. R. (2004). Ant colony optimization techniques for the vehicle routing problem. Advanced engineering informatics, 18(1), 41-48.
Berbeglia, G., Cordeau, J. F., & Laporte, G. (2010). Dynamic pickup and delivery problems. European journal of operational research, 202(1), 8-15.
Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99, 300-313.
Cai, X., Chen, J., Xiao, Y., Xu, X., & Yu, G. (2013). Fresh-product supply chain management with logistics outsourcing. Omega, 41(4), 752-765.
Cordeau, J. F., G. Laporte, M. W. P. Savelsbergh, & D. Vigo. (2007). Chapter 6 Vehicle Routing. Handbooks in Operations Research & Management Science 14: 367–428.
Dai, B., & Chen, H. (2012). Profit allocation mechanisms for carrier collaboration in pickup and delivery service. Computers & Industrial Engineering, 62(2), 633-643
Dai, B., Chen, H., & Yang, G. (2014). Price-setting based combinatorial auction approach for carrier collaboration with pickup and delivery requests. Operational Research, 14(3), 361-386.
Dror, M., & Trudeau, P. (1989). Savings by split delivery routing. Transportation Science, 23(2), 141-145.
Eksioglu, B., Vural, A. V., & Reisman, A. (2009). The vehicle routing problem: A taxonomic review. Computers & Industrial Engineering, 57(4), 1472-1483.
Farahani, P., Grunow, M., & Günther, H. O. (2012). Integrated production and distribution planning for perishable food products. Flexible services and manufacturing journal, 24(1), 28-51.
Fernández, E., Roca-Riu, M., & Speranza, M. G. (2018). The shared customer collaboration vehicle routing problem. European Journal of Operational Research, 265(3), 1078-1093.
Fraley, S., Oom, M., Terrien, B., & Date, J. (2006). Design of experiments via Taguchi methods: orthogonal arrays. The Michigan chemical process dynamic and controls open text book, USA, vol 2. No. 3. p 4.
Jiang, Y., Bian, B., & Liu, Y. (2020). Integrated multi-item packaging and vehicle routing with split delivery problem for fresh agri-product emergency supply at large-scale epidemic disease context. Journal of Traffic and Transportation Engineering (English Edition).
Gansterer, M., & Hartl, R. F. (2018). Collaborative vehicle routing: a survey. European Journal of Operational Research, 268(1), 1-12.
Gansterer, M., Küçüktepe, M., & Hartl, R. F. (2017). The multi-vehicle profitable pickup and delivery problem. OR Spectrum, 39(1), 303-319.
Ghilas, V., Demir, E., & Van Woensel, T. (2016). A scenario-based planning for the pickup and delivery problem with time windows, scheduled lines and stochastic demands. Transportation Research Part B: Methodological, 91, 34-51.
Govindan, K., Jafarian, A., Khodaverdi, R., & Devika, K. (2014). Two-echelon multiple-vehicle location–routing problem with time windows for optimization of sustainable supply chain network of perishable food. International Journal of Production Economics, 152, 9-28.
Goyal, S. K., & Giri, B. C. (2001). Recent trends in modeling of deteriorating inventory. European Journal of operational research, 134(1), 1-16.
Holland, J. H. (1992). Genetic algorithms. Scientific american, 267(1), 66-73
Hu, H., Zhang, Y., & Zhen, L. (2017). A two-stage decomposition method on fresh product distribution problem. International Journal of Production Research, 1-24.
Iassinovskaia, G., Limbourg, S., & Riane, F. (2017). The inventory-routing problem of returnable transport items with time windows and simultaneous pickup and delivery in closed-loop supply chains. International Journal of Production Economics, 183, 570-582.
Kachitvichyanukul, V., Sombuntham, P., & Kunnapapdeelert, S. (2015). Two solution representations for solving multi-depot vehicle routing problem with multiple pickup and delivery requests via PSO. Computers & Industrial Engineering, 89, 125-136.
Karaesmen, I. Z., Scheller–Wolf, A., & Deniz, B. (2011). Managing perishable and aging inventories: review and future research directions. In Planning production and inventories in the extended enterprise (pp. 393-436). Springer US
Laporte, G. (2009). Fifty years of vehicle routing. Transportation science, 43(4), 408-416.
Li, Y., Chen, H., & Prins, C. (2016). Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests. European Journal of Operational Research, 252(1), 27-38
Nahmias, S. (1982). Perishable inventory theory: A review. Operations research, 30(4), 680-708.
Nowak, M., Ergun, Ö., & White III, C. C. (2008). Pickup and delivery with split loads. Transportation Science, 42(1), 32-43.
Osvald, A., & Stirn, L. Z. (2008). A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food. Journal of food engineering, 85(2), 285-295.
Padmanabhan, B., Huynh, N., Ferrell, W., & Badyal, V. (2020). Potential benefits of carrier collaboration in vehicle routing problem with pickup and delivery. Transportation Letters, 1-16
Parragh, S. N., Doerner, K. F., & Hartl, R. F. (2008). A survey on pickup and delivery models part ii: Transportation between pickup and delivery locations. Journal für Betriebswirtschaft, 58(2), 81-117.
Rahimi, M., Baboli, A., & Rekik, Y. (2014, December). A bi-objective inventory routing problem by considering customer satisfaction level in context of perishable product. In Computational Intelligence in Production and Logistics Systems (CIPLS), 2014 IEEE Symposium on (pp. 91-97). IEEE.
Song, B. D., & Ko, Y. D. (2016). A vehicle routing problem of both refrigerated-and general-type vehicles for perishable food products delivery. Journal of Food Engineering, 169, 61-71.
Vaziri, S., Etebari, F., & Vahdani, B. (2019). Development and optimization of a horizontal carrier collaboration vehicle routing model with multi-commodity request allocation. Journal of Cleaner Production, 224, 492-505.
Verdonck, L., Caris, A. N., Ramaekers, K., & Janssens, G. K. (2013). Collaborative logistics from the perspective of road transportation companies. Transport Reviews, 33(6), 700-719.
Wang, C., Zhao, F., Mu, D., & Sutherland, J. W. (2013, September). Simulated annealing for a vehicle routing problem with simultaneous pickup-delivery and time windows. In IFIP international conference on advances in production management systems (pp. 170-177). Springer, Berlin, Heidelberg.
Wang, H. F., & Chen, Y. Y. (2013). A coevolutionary algorithm for the flexible delivery and pickup problem with time windows. International Journal of Production Economics, 141(1), 4-13.
Wang, X., Wang, M., Ruan, J., & Zhan, H. (2016). The Multi-objective Optimization for Perishable Food Distribution Route Considering Temporal-spatial Distance. Procedia Computer Science, 96, 1211-1220.
Wang, Y., Ma, X. L., Lao, Y. T., Yu, H. Y., & Liu, Y. (2014). A two-stage heuristic method for vehicle routing problem with split deliveries and pickups. Journal of Zhejiang University SCIENCE C, 15(3), 200-210.
Wang, Y., Ma, X., Xu, M., Liu, Y., & Wang, Y. (2015). Two-echelon logistics distribution region partitioning problem based on a hybrid particle swarm optimization–genetic algorithm. Expert Systems with Applications, 42(12), 5019-5031.
Wu, Q., Mu, Y., & Feng, Y. (2015). Coordinating contracts for fresh product outsourcing logistics channels with power structures. International Journal of Production Economics, 160, 94-105.
Zachariadis, E. E., Tarantilis, C. D., & Kiranoudis, C. T. (2015). The load-dependent vehicle routing problem and its pick-up and delivery extension. Transportation Research Part B: Methodological, 71, 158-181.
Zhang, Y., & Chen, X. D. (2014). An Optimization Model for the Vehicle Routing Problem in Multi-product Frozen Food Delivery. Journal of applied research and technology, 12(2), 239-250.
Zhang, W., Chen, Z., Zhang, S., Wang, W., Yang, S., & Cai, Y. (2020). Production, 274, 122593.