Routing optimization model for delivering multi meal products with time-dependent
Abstract views: 162
/ 
PDF downloads: 74
Keywords:
Vehicle routing problem, Heterogenic fleet, Time restricted, Feasible neighborhood search, Integer programmingAbstract
Catering is a popular business, particularly in big cities of Indonesia, such as Jakarta and Medan. This business can provide an alternative for office workers, households, and even school students to enjoy home-cooked food according to taste with many choices or variants. The catering distribution service must consider the time-dependent between each delivery to minimize the delivery time. This paper uses a time-dependent logistic system to find the best set of routes taken by a fleet of vehicles carrying meals to satisfy a particular group of clients concerning service time constraints, which could be expressed as a routing problem regarding a fleet of vehicles. The issue's primary goal is to reduce the overall travel costs (time or distance associated with travel) and operational costs (number of vehicles utilized). Because of the widely varying sizes of the demands from distinct types of clients, we have to deal with a heterogeneous vehicle fleet in this regard. Heterogeneous Vehicle Routing Problem (HVRP) is the name for this type of issue. The issue is described using an integer programming model. The model's solution is presented in this paper using a viable neighborhood technique based on a reduced gradient approach. We solve a heterogenous vehicle routing problem to show that the model and the method proposed for the catering distribution service is appropriate.
References
Balseiro, S. R., Loiseau, I., & Ramonet, J. (2011). An ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows. Computers & Operations Research, 38(6), 954–966.
Ban, M., Yu, J., Shahidehpour, M., Guo, D., & Yao, Y. (2019). Electric vehicle battery swapping-charging system in power generation scheduling for managing ambient air quality and human health conditions. IEEE Transactions on Smart Grid, 10(6), 6812–6825.
Beasley, J. E. (1981). Adapting the savings algorithm for varying inter-customer travel times.
Bräysy, O., & Gendreau, M. (2005). Vehicle routing problem with time windows, Part II: Metaheuristics. Transportation Science, 39(1), 119–139.
Cook, W., & Rich, J. L. (1999). A parallel cutting-plane algorithm for the vehicle routing problem with time windows.
Cordeau, J.-F., Laporte, G., & Mercier, A. (2001). A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 52(8), 928–936.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80–91.
Desrochers, M., Lenstra, J. K., & Savelsbergh, M. W. P. (1990). A classification scheme for vehicle routing and scheduling problems. European Journal of Operational Research, 46(3), 322–332.
Desrosiers, J., Dumas, Y., Solomon, M. M., & Soumis, F. (1995). Time constrained routing and scheduling. Handbooks in Operations Research and Management Science, 8, 35–139.
Duan, Z., Sun, S., Sun, S., & Li, W. (2015). Stochastic time-dependent vehicle routing problem: Mathematical models and ant colony algorithm. Advances in Mechanical Engineering, 7(11), 1687814015618631.
Ellabib, I., Basir, O. A., & Calamai, P. (2002). An experimental study of a simple ant colony system for the vehicle routing problem with time windows. International Workshop on Ant Algorithms, 53–64.
Figliozzi, M. A. (2012). The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics. Transportation Research Part E: Logistics and Transportation Review, 48(3), 616–636.
Franceschetti, A., Honhon, D., Van Woensel, T., Bektaş, T., & Laporte, G. (2013). The time-dependent pollution-routing problem. Transportation Research Part B: Methodological, 56, 265–293.
Gao, S., & Chabini, I. (2006). Optimal routing policy problems in stochastic time-dependent networks. Transportation Research Part B: Methodological, 40(2), 93–122.
Gendreau, M., & Tarantilis, C. D. (2010). Solving large-scale vehicle routing problems with time windows: The state-of-theart. Cirrelt Montreal.
Gmira, M., Gendreau, M., Lodi, A., & Potvin, J.-Y. (2021). Tabu search for the time-dependent vehicle routing problem with time windows on a road network. European Journal of Operational Research, 288(1), 129–140.
Golden, B., Assad, A., Levy, L., & Gheysens, F. (1984). The fleet size and mix vehicle routing problem. Computers & Operations Research, 11(1), 49–66.
Golden, B. L., & Assad, A. A. (1986). OR forum—perspectives on vehicle routing: exciting new developments. Operations Research, 34(5), 803–810.
Golden, B. L., Assad, A. A., & Wasil, E. A. (2002). Routing vehicles in the real world: applications in the solid waste, beverage, food, dairy, and newspaper industries. In The vehicle routing problem (pp. 245–286). SIAM.
Groër, C., Golden, B., & Wasil, E. (2009). The consistent vehicle routing problem. Manufacturing & Service Operations Management, 11(4), 630–643.
Harwood, K., Mumford, C., & Eglese, R. (2013). Investigating the use of metaheuristics for solving single vehicle routing problems with time-varying traversal costs. Journal of the Operational Research Society, 64(1), 34–47.
Hashimoto, H., Yagiura, M., & Ibaraki, T. (2008). An iterated local search algorithm for the time-dependent vehicle routing problem with time windows. Discrete Optimization, 5(2), 434–456.
Hill, A. V, & Benton, W. C. (1992). Modelling intra-city time-dependent travel speeds for vehicle scheduling problems. Journal of the Operational Research Society, 43(4), 343–351.
Hoff, A., Andersson, H., Christiansen, M., Hasle, G., & Løkketangen, A. (2010). Industrial aspects and literature survey: Fleet composition and routing. Computers & Operations Research, 37(12), 2041–2061.
Ichoua, S., Gendreau, M., & Potvin, J.-Y. (2003). Vehicle dispatching with time-dependent travel times. European Journal of Operational Research, 144(2), 379–396.
Jabali, O., Van Woensel, T., & De Kok, A. G. (2012). Analysis of travel times and CO2 emissions in time‐dependent vehicle routing. Production and Operations Management, 21(6), 1060–1074.
Ji, Y., Du, J., Wu, X., Wu, Z., Qu, D., & Yang, D. (2021). Robust optimization approach to two-echelon agricultural cold chain logistics considering carbon emission and stochastic demand. Environment, Development and Sustainability, 23(9), 13731–13754.
Keskin, M., Laporte, G., & Çatay, B. (2019). Electric vehicle routing problem with time-dependent waiting times at recharging stations. Computers & Operations Research, 107, 77–94.
Koç, Ç., Bektaş, T., Jabali, O., & Laporte, G. (2016). Thirty years of heterogeneous vehicle routing. European Journal of Operational Research, 249(1), 1–21.
Kok, A. L., Hans, E. W., & Schutten, J. M. J. (2012). Vehicle routing under time-dependent travel times: the impact of congestion avoidance. Computers & Operations Research, 39(5), 910–918.
Kumar, S. N., & Panneerselvam, R. (2012). A survey on the vehicle routing problem and its variants.
Kuo, Y. (2010). Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem. Computers & Industrial Engineering, 59(1), 157–165.
Kuo, Y., Wang, C.-C., & Chuang, P.-Y. (2009). Optimizing goods assignment and the vehicle routing problem with time-dependent travel speeds. Computers & Industrial Engineering, 57(4), 1385–1392.
Laporte, G., Louveaux, F., & Mercure, H. (1992). The vehicle routing problem with stochastic travel times. Transportation Science, 26(3), 161–170.
Larsen, J. (1999). Parallelization of the vehicle routing problem with time windows. Citeseer.
Lecluyse, C., Van Woensel, T., & Peremans, H. (2009). Vehicle routing with stochastic time-dependent travel times. 4OR, 7(4), 363–377.
Liu, C., Kou, G., Zhou, X., Peng, Y., Sheng, H., & Alsaadi, F. E. (2020). Time-dependent vehicle routing problem with time windows of city logistics with a congestion avoidance approach. Knowledge-Based Systems, 188, 104813.
Malandraki, C., & Daskin, M. S. (1992). Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms. Transportation Science, 26(3), 185–200.
Miller-Hooks, E., & Mahmassani, H. (2003). Path comparisons for a priori and time-adaptive decisions in stochastic, time-varying networks. European Journal of Operational Research, 146(1), 67–82.
Mourgaya, M., & Vanderbeck, F. (2006). The periodic vehicle routing problem: classification and heuristic. RAIRO-Operations Research, 40(2), 169–194.
Nahum, O. E., & Hadas, Y. (2009). Developing a model for the stochastic time-dependent vehicle-routing problem. 2009
International Conference on Computers & Industrial Engineering, 118–123.
Prakash, A. A. (2018). Pruning algorithm for the least expected travel time path on stochastic and time-dependent networks.
Transportation Research Part B: Methodological, 108, 127–147.
Rabbani, M., Navazi, F., Farrokhi-Asl, H., & Balali, M. (2018). A sustainable transportation-location-routing problem with soft time windows for distribution systems. Uncertain Supply Chain Management, 6(3), 229–254.
Rajabi-Bahaabadi, M., Shariat-Mohaymany, A., Babaei, M., & Ahn, C. W. (2015). Multi-objective path finding in stochastic time-dependent road networks using non-dominated sorting genetic algorithm. Expert Systems with Applications, 42(12), 5056–5064.
Respen, J., Zufferey, N., & Potvin, J.-Y. (2019). Impact of vehicle tracking on a routing problem with dynamic travel times. RAIRO-Operations Research, 53(2), 401–414.
Rincon-Garcia, N., Waterson, B., & Cherrett, T. (2017). A hybrid metaheuristic for the time-dependent vehicle routing problem with hard time windows. International Journal of Industrial Engineering Computations, 8(1), 141–160.
Sarasola, B., Doerner, K. F., Schmid, V., & Alba, E. (2016). Variable neighborhood search for the stochastic and dynamic vehicle routing problem. Annals of Operations Research, 236(2), 425–461.
Savelsbergh, M., & Van Woensel, T. (2016). 50th anniversary invited article—city logistics: Challenges and opportunities. Transportation Science, 50(2), 579–590.
Shi, Y.-J., Meng, F.-W., & Shen, G.-J. (2012). A modified artificial bee colony algorithm for vehicle routing problems with time windows. Information Technology Journal, 11(10), 1490.
Soysal, M., Bloemhof-Ruwaard, J. M., & Bektaş, T. (2015). The time-dependent two-echelon capacitated vehicle routing problem with environmental considerations. International Journal of Production Economics, 164, 366–378.
Tan, K. C., Lee, L. H., Zhu, Q. L., & Ou, K. (2001). Heuristic methods for vehicle routing problem with time windows. Artificial Intelligence in Engineering, 15(3), 281–295.
Tan, X., Luo, X., Chen, W. N., & Zhang, J. (2005). Ant colony system for optimizing vehicle routing problem with time windows. International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce (CIMCA-IAWTIC’06), 2, 209–214.
Taş, D., Dellaert, N., van Woensel, T., & De Kok, T. (2014). The time-dependent vehicle routing problem with soft time windows and stochastic travel times. Transportation Research Part C: Emerging Technologies, 48, 66–83.
Toth, P., & Vigo, D. (2002a). SIAM monographs on discrete mathematics and applications: the vehicle routing problem.
Philadelphia: SIAM.
Toth, P., & Vigo, D. (2002b). The vehicle routing problem. SIAM.
Vidal, T., Crainic, T. G., Gendreau, M., Lahrichi, N., & Rei, W. (2012). A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3), 611–624.
Vodopivec, N., & Miller-Hooks, E. (2017). An optimal stopping approach to managing travel-time uncertainty for time-sensitive customer pickup. Transportation Research Part B: Methodological, 102, 22–37.
Wang, C., Mu, D., Zhao, F., & Sutherland, J. W. (2015). A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows. Computers & Industrial Engineering, 83, 111–122.
Wang, F., Liao, F., Li, Y., Yan, X., & Chen, X. (2021). An ensemble learning based multi-objective evolutionary algorithm for the dynamic vehicle routing problem with time windows. Computers & Industrial Engineering, 154, 107131.
Zhang, T., Chaovalitwongse, W., & Zhang, Y. (2014). Integrated ant colony and tabu search approach for time dependent vehicle routing problems with simultaneous pickup and delivery. Journal of Combinatorial Optimization, 28(1), 288–309.
