Journal of Transportation Research

Journal of Transportation Research

Proper Routing of Vehicles Along with Hub Location and Time Window with the Help of Innovative Algorithms (Case Study: Tobacco Company)

Document Type : Original Article

Authors
Rasoul Nematniya 1
Maryam Khademi 2
Kyamars Fathi 3
Sohela Sardar 1
1 Department of Industrial Management, Azad University, North Tehran Branch, Tehran, Iran.
2 Faculty of Engineering, Islamic Azad University, South Tehran Branch, Tehran, Iran.
3 Department of Industrial Management, Azad University, South Tehran Branch, Tehran, Iran.
10.22034/tri.2024.447410.3234
Abstract
Routing is one of the most important issues in designing distribution networks that reduces costs. The purpose of this issue is to meet the demands of customers and minimize costs, including routing, transportation, facilitation and operational costs. Hubs that act as distribution intermediaries are distribution centers and strategic points. In distribution networks with facilities at the origin and destination, they show us according to the problem, the location of the warehouses as a hub is effective in determining the route of the equipment and the related cost, so the production units with location for Distribution warehouses and vehicle routing reduce costs.By looking at the two problems of routing and locating for distribution, it is possible to provide an optimal answer for both problems.The aim of this research is to provide a model for distributing products by simultaneously considering routing and location, in order to reduce costs and reduce environmental damage. Also, customers have a limited time window and the service must be done within the time frame. Exact and meta-heuristic methods, epsilon constraint and multi-objective optimization are used to solve the models. The results show that the proposed method of the study has an acceptable performance and reduces the time to reach the optimum in new routes by a third, the number of centers from 26 to 10, and the number of cars from 59 to 42. Finally, in order to bring the research closer to the real world conditions, the model is implemented on the data of the tobacco company.In the state before the model, the value of the function is equal to 1550222/60, the model presented using the multi-objective particle optimization method, the result is equal to 1331400/15, which shows approximately 218822 units of cost reduction.
Keywords
Transportation
Routing
Location
Hub Network
Meta-Innovation
Subjects
-Baldacci, r., hadjiconstantinou, e., mingozzi, a., (2004). An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Oper. Res. 52 (5), 723–738.
-Baldacci, r., mingozzi, a., (2009). A unified exact method for solving different classes of vehicle routing problems. Math. Program. 120, 347–380.
-Balseiro, s.r., loiseau, i., ramonet, J., (2011). An ant colony algorithm hybridized with insertion heuristic for the time dependent vehcile routing problem with time windows. Comput. Oper. Res. 38 (6), 954–966.
-Bezerra, s.n., souza, s.r., souza, m.J.f., (2018). A gvns algorithm for solving the multi-depot vehicle routing problem. Eletron. Notes Discrete Math. 66 (4), 167–174.
-Çimen, m., soysal, m., (2019). time-dependent green vehicle routing problem with stochastic vehicle spreed: an approximate dynamic programming algorithm. Transp. Res. d 54, 82–98.
-Clarke, g., wright, J., (1964). Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12, 568–581.
-Contardo, c., martinelli, r., (2014). A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints. Discrete Optim. 12, 129–146.
-Darvish, m., archetti, c., coelho, l.c., (2019). Trade-offs between environmental and economic performance in production and inventory-routing problems. Int. J. Prod. Econ. 217, 269–280.
-Darvish, m., coelho, l.c., (2018). Sequential versus integrated optimization: production, location, inventory control, and distribution. European J. Oper. Res. 268 (1), 203–214.
-Demir, e., bektaş, t., laporte, g., (2011). A comparative analysis of several vehicle emission models for road freight transportation. Transp. Res. D 16 (5), 347–357.
-Demir, e, bektaş, t., laporte, g., (2012). An adaptative large neighborhood search heuristic for the pollution-routing problem. European J. oper. res. 223, 346–359.
-Donati, a.v., montemanni, r., casagrande, n., rizzoli, a.e., gambardella, l.m., (2008). Time dependent vehicle routing problem with a multi ant colony system. European J. oper. res. 185 (3), 1174–1191.
-Fan, h., zhang, y., tian, p., Lv, y., fan, h., (2021). Time-dependent multi-depot green vehicle routing problem with time windows considering temporal-spatial distance. Comput. Oper. Res. 129.
-Figliozzi, M.A., (2012). The time dependent vehicle routing problem with time windows: benchmark problems, an efficient solution algorithm, and solution characteristics. Transp. Res. E 48 (3), 616–636.
-Fu, y., wu, d., wang, y., wang, h., (2020). Facility location and capacity planning considering policy preference and uncertain demand under the one belt one road initiative. Transp. Res. A 138, 172–186.
-Gendreau, m., ghiani, g., guerriero, e., (2015). Time-dependent routing problems, a review. Comput. Oper. Res. 64, 189–197.
-Golden, b., Assad, a., levy, l., gheysens, f., (1984). the fleet size and mix vehicle routing problem. Comput. Oper. Res. 11 (1), 49–66.
-Haghani, a., Jung, s., (2005). A dynamic vehicle routing problem with time-dependent travel times. Comput. Oper. Res. 32 (11), 2959–2986.
-Hardwood, k., mumford, c., eglese, r., (2013). Investigating the use of metaheuristics for solving single vehicle routing problems with time-varying traversal costs. J.oper. res. soc. 64 (1), 34–47.
-Heni, h., coelho, l., renaud, J., (2019). Determining time-dependent minimum cost paths under several objectives. Comput. Oper. Res. 105, 102–117.
-Ho, w., ho, g., Ji, p., lau, h., (2008). A hybrid genetic algorithm for the multi-epot vehicle routing problem. Eng. Appl. Artif. Intell. 21, 548–557.
-Huang, y.x., zhao, l., woensel, t.v., gross, J. p., (2017). Time-dependent vehicle routing problem with path flexibility. Transp. Res. B 95, 169–195.
-Ichoua, s., gendreau, m., Potvin, J. y., (2003). Vehicle dispatching with time-dependent travel times. European J. oper. res. 144 (2), 379–396.
-Jaballah, r., veenstra, m., coelho, l.c., renaud, J., (2021). The time-dependent shortest path and vehicle routing problem infor inf. syst. oper. res. 59 (4), 592–622.
-Koç, c., bektaş, t., Jabali, o., laporte, g., (2016a). The fleet size and mix location-routing problem with time windows: formulations and a heuristic algorithm. European J. oper. res. 248 (1), 33–53.
-Kok, a., hans, e., schutten, J., (2012). Vehicle routing under time-dependent travel times: the impact of congestion avoidance. Comput. Oper. Res. 39 (5), 910–918.
-Kuo, y., (2010). Using simulated annealing to minimize fuel consumption for the time-dependent emission in urban areas. Comput. Ind. Eng. 59 (1), 157–165.
-Lahyani, r., coelho, l., renaud, J., (2018). Alternative formulations and improved bound for the multi-depot fleet size and mix vehicle routing problem. Spectrum 40, 125–157.
-Laporte, g., nobert, y., taillefer, s., (1988). Solving a family of multi-depot vehicle routing and location-routing problems. Transp. Sci. 22 (3), 161–172.
-Li, J., wang, r., li, t., lu. z., pardalos, p.m., (2018). Benefit analysis of shared depot resources for multi-depot vehicle routing problem with fuel consumption. Transp.Res. D 59, 417–432.
-Liu, c., kou, g., zhou, x., sheng, h., alsaadi, f.e., (2020). Time-dependent vehicle routing problems with time windows iof city logistics with a congestion avoidance approach. knowl. based syst. 188.
-Malandraki, c., daskin, m., (1992). Time dependent vehicle routing problems: formulations, properties and heuristic algorithms. Transp. Sci. 26 (3), 185–200.
-Mancini, s., (2016). A real-life multi depot multi period vehicle routing problem with a heterogeneous fleet: formulation and adaptive large neighborhood search based mataheuristic, Transp. Res. C 70, 100–112.
-Montoya-torres, J., franco, J.l., isaza, s.n., Jimenez, h.f., herazo-padilla, n., (2015). A literature review on the vehicle routing problem with multiple depots. Comput. Ind. Eng. 79, 115–129.
-Oliveira, f.b., enayatifar, r., sadaei, h.J., guimarães, f.g., potvin, J.y., (2016). A cooperative coevolutionary algorithm for the multi-depot vehicle routing problem. Expert Syst. Appl. 43, 117–130.
-Qian, J., eglese, r., (2016). Fuel emission optimization in vehicle routing problems with time-varying speeds. European J. oer. res. 248 (3), 840–848.
-Rahimi-vahed, a., cranic, t.g., gendreau, m., Rei, w., (2015). Fleet-sizing for multidepot and periodic vehicle routing problems using modular heuristic algorithm. Comput. Oper. Res. 53, 9–23.
-Ramos, t.r.p., gomes, m.i., póvoa, a.p.b., (2020). Multi-depot vehicle routing problem: a comparative study of alternative formulations. Int. J. Logist. Res. Appl. 23 (2), 103–120.
-Renaud, J., boctor, f., (2002). A sweep-based algorithm for the fleet size and mix vehicle routing problem. European J. Oper. Res. 140 (3), 618–628.
-Rincon-garcia, n., waterson, b., cherrett, t.J., salazar-arrieta, f., (2020). Ametaheuristic for the time-dependent vehicle routing problem considering driving hour regulations – an application in city logistics. Transp. Res. A 137, 429–446.
-Ropke, s., pisinger, d., (2006). An adaptative large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp. Sci. 40, 455–472.
-Sadati, m.e.h., catay, b., aksen, d., (2021). An efficient variable neighborhood search with tabu shaking for a class of multi-depot vehicle routing problems. Comput. Oper. Res. 133.
-Sadykov, r., uchoa, e., Pessoa, a, (2021). A bucket graph-based labeling algorithm with application to vehicle routing. Transp. Sci. 55 (1), 4–28.
-Salhi, s., imran, a., wassan, n., (2014). The multi-depot vehicle routing problem with heterogeneous vehicle fleet: formulation and a variable neighborhood search implementation. Comput. Oper. Res. 52, 315–325.
-Salhi, s., sari, m., (1997). A multi-level composite heuristic for the multi-depot vehicle fleet mix problem. European J. Oper. Res. 103 (1), 95–112.
-Savelsbergh, m., van woensel, t., (2016). 50th an niversary invited articlecity logistics: challenges and opportunities. Transp. Sci. 50 (2), 579–590.
Schmidt, c., silva, a., darvish, m., coelho, l., (2019). The time-dependent location-routing problem. Transp. Res. E 128, 193–315.
-Setak, m., habibi, m., karimi, h., abedzadeh, m., (2015). A time-dependent vehicle routing problem in multigraph with fifo property. J. Manuf. Syst. 35, 37–45.
-Snoeck, a., winkenbach, m., (2020). The value of physical distribution flexibility in serving dense and uncertain urban markets. transp. res. a 136, 151–177.
-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. Transp. Res. C 48, 66–83.
-Toth, P., Vigo, d. (eds.), (2014). Vehicle routing monographs on discrete mathematics and applications, mos-siam series on optimization, Philadelphia.
-Vidal, t., crainic, t., gendreau, m., lahrichi, n., rei, w., (2012). A hybrid genetic algorithm for multi-depot and periodic vehicle routing problems. Oper. Res. 60, 611–624.
Vidal, t., crainic, t., gendreau, m., prins, c., (2014). Implicit depot assignments and rotations in vehicle routing heuristics. European J. Oper. Res. 237 (1), 15–28.
-Xiao, y., konak, a., (2016). The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion. Transp. Res. E 88, 146–166.
-Xu, z., elomri, a., pokharel, s., mutlu, f., (2019). A model for capacitated green vehicle routing problem with the time-varying speed and soft time windows. Comput. Ind. Eng. 137.
-Yu, b., yang, z., xie, J., (2011. a parallel improved ant colony optimization for multi depot vehicle routing problem. J. oper. res. soc. 62 (1), 183–188.