VEHICLE ROUTING IN THE CASE OF UNCERTAIN CUSTOMER DEMANDS AND SOFT TIME WINDOWS: A NEURO-FUZZY LOGIC APPROACH
Abstract
Vehicle routing, with its many variants, is one of the most important and frequently solved problems in transportation engineering. The aim of this paper is to develop a decision-making support tool for addressing the issue of dispatching vehicles in scenarios characterized by uncertain demands within soft time windows. In real-world scenarios, it is not uncommon for customer demands to exhibit flexibility, where certain early arrivals or delays may be deemed acceptable. Therefore, this paper introduces vehicle routing in more realistic contexts, offering potential practical implementations. The methodology for solving the problem is based on a fuzzy logic system whose membership functions are additionally adjusted using a neural network. Such a tool, neuro-fuzzy logic, is suitable for solving a defined routing problem since it can consider all the mentioned uncertainties in the distribution systems. Each user is assigned a performance index that considers travel time, demand, and delivery time windows. Then, the performance index is used as input data in the proposed vehicle routing tool based on the Clarke-Wright algorithm. The described approach has been tested on a concrete example, mimicking a distribution network resembling real-world conditions, incorporating estimated travel times between customers. The results demonstrate that the proposed approach can effectively handle customer demands, with an average delay of 5.05 minutes during the 80-minute distribution. In future research, some environmental factors could be included in the proposed model. In addition, one of the directions of future research could be vehicle re-routing using the ideas from this paper.
References
U.S. Transportation. Climate Impact Index, ranking the top 100 metro areas in the United States. (2019), from https://www.streetlightdata.com/, accessed on 2023-05-06.
Sawik B, Faulin J, Pérez-Bernabeu E. (2017). Multi-criteria optimization for fleet size with environmental aspects. Transportation Research Procedia, vol. 27, 61-68. DOI: https://doi.org/10.1016/j.trpro.2017.12.056
Qian J, Eglese R. Fuel emissions optimization in vehicle routing problems with time-varying speeds. (2016). European Journal of Operational Research, vol. 248, no. 3, 840-848. DOI: https://doi.org/10.1016/j.ejor.2015.09.009
Zadeh L. (1965). Fuzzy sets. Information and Control, vol.8, 338–353.
Jang JS. (1993). ANFIS: adaptive-network-based fuzzy inference system. IEEE Transactions on Systems, Man, and Cybernetics, vol. 23, no. 3, 665-685. DOI: 10.1109/21.256541
Balinski ML, Quandt RE. (1964). On an integer program for a delivery problem. Operations Research, vol. 12, no. 2, 300-304. DOI: https://doi.org/10.1287/opre.12.2.300
Laporte G, Nobert Y. (1987). Exact algorithms for the vehicle routing problem. North-Holland Mathematics Studies, vol. 132, 147-184. DOI: https://doi.org/10.1016/S0304-0208(08)73235-3
Prins C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, vol. 31, no. 12, 1985-2002. https://doi.org/10.1016/S0305-0548(03)00158-8
Toth P, Vigo D. (2002). An overview of vehicle routing problems. In The vehicle routing problem. Philadelphia, USA: Society for Industrial and Applied Mathematics.
Konstantakopoulos GD, Gayialis SP, Kechagias EP. (2020). Vehicle routing problem and related algorithms for logistics distribution: A literature review and classification. Operational Research, vol. 22, 2033-2062.
Dantzig GB, Ramser JH. (1959). The truck dispatching problem. Management Science, vol. 6, no. 1, 80-91. DOI: https://doi.org/10.1287/mnsc.6.1.80
Christofides NA. (1979). The vehicle routing problem. Combinatorial Optimization.
Laporte G, Semet F. (2002). Classical heuristics for the capacitated vehicle routing problem. Philadelphia, USA: Society for Industrial and Applied Mathematics.
Gendreau M. (2002). Metaheuristics for the capacitated vehicle routing problem. Philadelphia, USA: Society for Industrial and Applied Mathematics.
Cordeau JF, et al. (2004). New heuristics for the vehicle routing problem. GERAD Montreal, Canada. Report number: G-2004-33.
Mester D, Braysy O. (2005). Active guided evolution strategies for large-scale vehicle routing problems with time windows. Computers & Operations Research, vol. 32, 1593-1614. DOI: https://doi.org/10.1016/j.cor.2003.11.017
Potvin JY, et al. (2005). The vehicle routing problem with time windows part I: Tabu search. INFORMS Journal on Computing, vol. 8, no. 2, 158-164. DOI: https://doi.org/10.1287/ijoc.8.2.158
Chiang WC, Russell R. (1996). Simulated annealing meta-heuristics for the vehicle routing problem with time windows. Annals of Operations Research, vol. 93, no. 1, 3-27.
Thangiah SR, et al. (1991). GIDEON: A Genetic Algorithm System for routing problems with time windows. Proceedings of the 7th IEEE Conference on Artificial Intelligence Applications 1991, Miami Beach, FL, USA. p. 322-328.
Potvin JY, Bengio S. (1996). The vehicle routing problem with time windows part II: Genetic Search. INFORMS Journal on Computing, vol. 8, no. 2, 165-172. DOI: https://doi.org/10.1287/ijoc.8.2.165
Nikolić M, Teodorović D. (2015). The vehicle rerouting problem with time windows and split delivery. Proceedings of the 2nd Logistics International Conference 2015, Belgrade, Serbia. 2015. p. 55-60.
Taillard E, et al. (1997). A Tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science, vol. 31, no. 2, 170-186. DOI: https://doi.org/10.1287/trsc.31.2.170
Figliozzi MA. (2010). An iterative route construction and improvement algorithm for the vehicle routing problem with soft time windows. Transportation Research Part C: Emerging Technologies, vol. 18, no. 5, 668-679. DOI: https://doi.org/10.1016/j.trc.2009.08.005
Tang J, et al. (2009). Vehicle routing problem with fuzzy time windows. Fuzzy Sets and Systems, vol. 160, no. 5, 683-695. DOI: https://doi.org/10.1016/j.fss.2008.09.016
Teodorović D, Pavković G. (1996). The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain. Fuzzy Sets and Systems, vol. 82, no. 3, 307-317. DOI: https://doi.org/10.1016/0165-0114(95)00276-6
Lučić P, Teodorović D. (2003). Vehicle routing problem with uncertain demand at nodes: The bee system and fuzzy logic approach. In: Verdegay JL. (eds.) Fuzzy sets based heuristics for optimization. Berlin, Heidelberg: Springer, p. 67-82. DOI: https://doi.org/10.1007/978-3-540-36461-0_5
Sungur I, Ordónez F, Dessouky M. (2008). A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. IIE Transactions, vol. 40, no. 5, 509-523.DOI: https://doi.org/10.1080/07408170701745378
Tas D, et al. (2013). Vehicle routing problem with stochastic travel times including soft time windows and service costs. Computers & Operations Research, vol. 40, no. (1), 214-224. DOI: https://doi.org/10.1016/j.cor.2012.06.008
Xu J, Yan F, Li S. (2011). Vehicle routing optimization with soft time windows in a fuzzy random environment. Transportation Research Part E: Logistics and Transportation Review, vol. 47, no. 6, 1075-1091. DOI: https://doi.org/10.1016/j.tre.2011.04.002
Yang T, Wang W, Wu Q. (2022). Fuzzy demand vehicle routing problem with soft time windows. Sustainability, vol. 14, no. 9, 5658. DOI: https://doi.org/10.3390/su14095658
Khodashenas M, et al. (2023). Providing an integrated multi-depot vehicle routing problem model with simultaneous pickup and delivery and package layout under uncertainty with fuzzy-robust box optimization method. Decision Making: Applications in Management and Engineering, vol. 6, no. 2, 372-403. DOI: https://doi.org/10.31181/dmame622023640
Yadegari Z, et al. (2024). Designing a Fuzzy Mathematical Model for a Two-Echelon Allocation-Routing Problem by Applying Route Conditions: A New Interactive Fuzzy Approach. Decision Making: Applications in Management and Engineering, vol. 7, no. 2, 172-196. DOI: https://doi.org/10.31181/dmame7220241029
Munjal P, Pahl J. (1969). An analysis of the Boltzmann-type statistical models for multi-lane traffic flow. Transportation Research, vol. 3, no. 1, 151-163.
Highway Capacity Manual (HCM). (2010). Transportation Research Board. National Research Council, Washington, DC.
Dijkstra EW. (1959). A note on two problems in connection with graphs. Numerische Mathematik, vol.1, no. 1, 269-271.
Rumelhart DE, Hinton GE, Williams RJ. (1985). Learning internal representations by error propagation. California University San Diego La Jolla Institut for Cognitive Science. Report number: ICS-8506.
Clarke G, Wright JW. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, vol. 12, no. 4, 568-581. DOI: https://doi.org/10.1287/opre.12.4.568
