A Decision Support System (DSS) for the heuristic allocation and routing of vehicles in urban freight transportation

Abstract

Abstract: Solve a strategic operational problem for a company, requires mathematical modeling and computing power, therefore, it requires computational tools that contribute to decision support system (DSS). Keywords: Decision Support System, urban freight transportation, large-scale optimization, vehicle routing problem, heuristics, metaheuristics. 1.Introduction All production and distribution companies have problems associated with logistics operation and distribution. To contribute to this very important real-life combinatorial optimization problem, we propose the design and development of a decision support system (DSS). [...]Section 4 presents a case of real-world DSS application. 2.

Headnote

Abstract: Solve a strategic operational problem for a company, requires mathematical modeling and computing power, therefore, it requires computational tools that contribute to decision support system (DSS). The development for the suboptimal planning and distribution of freight vehicles in its logistics network is presented. It is considered contributing to two problems NP-Hard, the allocation (strategic) and routing of vehicles with time intervals for deliveries to the customer locations (operative, known as VRPTW) in order to minimize the total travel time and cost of the logistics operation, with capacity restrictions and client's time intervals for deliveries. Furthermore, the research considers data obtained from real scenarios, which is why they are classified as combinatorial problems on a large scale. The logistics problem involved in urban freight transportation is approached as a VRPTW, where several optimization algorithms are used to solve sub-models of the mayor complex model, resulting in hybrid solution approach that involves metaheuristics and heuristics. By using the Snow methodology, which considers cases of a company, a web-based application is developed, such as a successful DSS, which allows suboptimal solution to large-scale problems and the improvement in the urban freight logistic problem in a city of Colombia.

Keywords: Decision Support System, urban freight transportation, large-scale optimization, vehicle routing problem, heuristics, metaheuristics.

1.Introduction

All production and distribution companies have problems associated with logistics operation and distribution. This affects not only their total operation costs (Ballou, 2004) but also the goodwill gained among their clients. Companies require that their processes be more efficient. However, processes require extensive tasks to identify, remove, manipulate and interpret the elements involved, in particular for freight logistics. Nowadays, urban freight transportation is considered a very difficult and complex activity. Especially in urban cities, where there are problems associated with traffic control, congestion, and environmental aspects (Dablanc, 2007; Holguín-Veras et al., 2018). The situation in the downtown areas of cities is a critical issue and is not going to get any better. Traffic conditions are getting worse, either because of an increased number of vehicles, or the lack of infrastructure capacity that affects the quality of life (Crainic et al., 2016). Intelligent Transportation Systems (ITS) and technologies are called to support this type of issue by controlling the routing of freight vehicles within the city, and thus, support private freight companies in their decision-making process. Making decisions about the optimal planning of the logistics network in urban freight transportation brings up an important point which is vehicle routing. This problem has been studied broadly given that transportation is one of the most critical aspects of the logistics operation of a company (Cattaruzza et al., 2017; Hesse & Rodrigue, 2004).

The vehicle routing problem with time windows (VRPTW) is one of the most studied problems in vehicle routing, since it nearly represents the real transportation issues managed by most companies, especially concerning urban freight transportation (Pecin et al., 2017; Vigo & Toth, 2014). As cited by (Bodin et al., 1981), the VRPTW problem is used to model numerous real-life applications. It considers the allocation of each vehicle to a route, where all customers are visited within their time frames respecting the capacity of the vehicles allocated (Bodin et al., 1981). The complexity of the VRPTW is NP-hard since this problem can be decomposed into two sub-problems. One is a multiprocessor scheduling problem with some form of sequence-dependent service times, and the other is a bin-packing problem, both of them considered NP-complete.

Trying to solve this type of vehicle routing problem and getting an efficient algorithm that solves large-scale problems is not an easy task. Solution methods for the VRPTW span from exact methods such as a branch and bound approach (Bard et al., 2002) to metaheuristic approaches such as Tabu Search (Gendreau et al., 1999), Ant Colony Systems (Gambardella et al., 1999), Evolutionary Algorithms (Garcia-Najera & Bullinaria, 2011), Particle Swarm Optimization (Masrom et al., 2015) among others (Saeheaw & Charoenchai, 2016). Yet, when approaching real-life transportation problems many other aspects must be considered and not all the solution approaches are acceptable given the large amount of data involved.

To contribute to this very important real-life combinatorial optimization problem, we propose the design and development of a decision support system (DSS). The DSS was developed in a web environment, where the back-end has metaheuristic hybrid algorithms that allow finding suboptimal solutions in a prudent computational time. The solution was then applied to solve the large-scale problems of a company dedicated to the distribution of products in a city of Colombia. The main goal of the application is to minimize the total travel time and the cost of logistics operations.

The paper is organized as follows. Section 1 presents the problem under study and the related literature. The design of the DSS is described in Section 2, while section 3 is dedicated to present the hybrid metaheuristic approach programmed in the DSS. Finally, Section 4 presents a case of real-world DSS application.

2. Design a DSS

A DSS must respond to functional and non-functional requirements in real business scenarios. To develop software of quality, the project of applied research use the methodology Snow based in use case (Jacobson, 1992; Sánchez-Dams, 2014) that can address up to level three of process improvement Capability Maturity Model Integration (CMMI) v1.3 (Chrissis et al., 2011). Snow is based a top down method, where more complex problems are subdivided in atomic parts, until find the general solution. Every part of life cycle of develop is predetermined for tasks must are validated by expert (Maropoulos & Ceglarek, 2010).In particular, the tasks are related to functions associated to allocation and distribution problem, for give the final user a holistic solution of logistics operation.

The DSS is composed by several modules: user configuration, security, distribution planning and vehicle dispatching. In both the distribution planning and vehicle dispatching modules, optimization algorithms are integrated which determine the heuristic allocation of their fleet of vehicles and their routes to take at a daily basis. In order to obtain this, the modules consist of several key activities where algorithms were incorporated. The model data is stored in a MySql database using Laravel migration structure. Furthermore, a map engine is used to find geographic information and represent it. The WEB server characteristics are: Ubuntu Linux operating system v14: 04, with 2 gigabytes of RAM and 10 gigabytes of hard drive, running in elastic Amazon Web Service (AWS). The resulting software developed is a web application that works for large amount of data from different server platforms and transform it as input data

3. A hybrid metaheuristic approach to optimized in DSS

In the back end of web application, a hybrid optimization algorithm was integrated as a decision-making procedure. The method contemplates two metaheuristics, Evolutionary Particle Swarm Optimization (EPSO) was used to obtain the best location-routing configuration with multiple depots, and Ant Colony Optimization (ACO) employed to solve the VRPTW. Other restrictions are incorporated such as traffic conditions, restricted hours and specific routes for vehicle transit in urban areas. A hybrid solution approach, consisting of the following steps, depicted in Figure 1:

3.1. Evolutionary Particle Swarm Optimization Algorithm

The Evolutionary Particle Swarm Optimization (EPSO) was considered to obtain the suboptimal location of the multiple depots at a strategic level and the distribution of clients to the different depot locations, based the demand for products and the capacity of these locations and vehicles. Was used a particle to represent the solution and replicates and mutates the particles, measuring the velocity of each particle according the best value measured in their objective function. The algorithm are presents in Algorithm 1.

3.2. Ant Colony Optimization algorithm

The Ant Colony Optimization (ACO) algorithm is used an approach to solve the VRPTW, where each route is probabilistically determined by the pheromone trail left by the generation of ants the preceded. Each ant agent depicted a vehicle where the route is constructed, according a set of possible client nodes available. The equation (1) determines if the client node j is chosen or not, given pheromone level between node i and j, distance djj and a priority parameter. The algorithm are presents in Algorithm 2.

(ProQuest: ... denotes formula omitted.) (1)

4.Case of real-world application

Applied research takes place in Barranquilla, a city that is strategically located in the northern coast of Colombia, the increase in foreign trade has numbered the transactions of merchandise in and out of the country through the Atlantic Ocean. Yet, the lack of railroad infrastructure and other modes of transportation, makes ground transportation is only way to move merchandise across the country.

This tool was applied to different types of businesses that operate in Barranquilla, where their freight operations were done at an urban scale and decisions are made on a daily basis. Computational results show the impact of web applications for urban freight transportation and the great influence that optimization algorithms give to decision making. Based on the analysis of historical data from the operation of transportation companies, potential improvements are proved with the web application in the process of planning and operational distribution.

The current operation of this company makes use of a heterogeneous fleet of four vehicles as presented in the Table 1. With the set of orders that have to be delivered in a given day, the company makes use of all its four vehicles to visit the customers and meet their demands. This allocation of customers to vehicles is made assigning to each vehicle the customers according to predefined geographical zones. The truck driver then uses his experience in order to determine the route and sequence in which orders are to be delivered. Nevertheless, the travelling route and sequence is not registered. The Table 1 shows how in one of the cases the capacity restriction by vehicle 4 is violated.

By implementing our approach, assigning orders and calculating the routes using the web application, the number of vehicles needed in the distribution operation is reduced to only two vehicles as shown in the Table 2. The optimization of the vehicle fleet needed clearly reduces operative costs of maintenance, tire wear, driver wages and fuel.

In the case of the solution implemented by the company, the allocation of customers to the vehicles is made by assigning different geographical zones to each vehicle. Since there is no record of the route built by the truck driver, the route construction for the solution implemented by the company was also made by using the Ant Colony Optimization Procedure. Hence, we compare the allocation by geographical zones implemented by the company, building the routes for this scenario, and assuming that the routes built by the truck drivers were optimal, versus the solution proposed by the tool were allocation and routing processes are made by the Ant Colony Optimization procedure.

The results show that the solution obtained by the tool reduces the number of vehicles needed by 50% and the total travelled distance by 13.78%. This savings represents an important reduction in time, fuel and staff cost for the company. Similar results were found implementing the proposed tool in the operations of some other transportation companies. As shown by the numerical results, today's business operations lack of an optimal allocation and distribution of merchandize at cities. The tool proved to outperform the actual business scenario, which show the successful implementation of optimization algorithms to complex problems such as the VRPTW. The tool also proved to generate fast results, which makes it feasible for decision making at a daily basis.

4. Conclusions

Urban freight transportation has been a very complex and costly operation in most businesses. The key to an efficient operation lies on the most adequate planning and distribution of their merchandise. The results obtained from the implementation of a decision support system (DSS) for this type of businesses indicate that there is much to be improved in today's logistics operations and that the use of metaheuristics is the key to obtaining an optimal planning and distribution of freight vehicles in its logistics network at an urban scale. In order to minimize the total travel time and cost of the logistics operation, the solution offered by the DSS was based on the allocation and routing of vehicles to the customer location, associated to the different orders and respecting their time windows.

As this logistics problem is considered NP-hard and the data used to make decisions is quite substantial, technology is a main issue. An appropriate methodology and architecture defined the successful implementation of the solution at an enterprise level. Given the complexity at an algorithmic point of view, a hybrid solution approach which consisted on solving the large problem in smaller sub-problems by several metaheuristics and heuristics, resulted in an efficient performance of the decision-making tool.

The DSS approaches a large-scale optimization problem that involves complex operations at a daily basis and implementation results prove to improve today's urban freight operations to a group of businesses in Barranquilla, Colombia, with a potential of solving the urban transportation problem in other cities nationwide and at international level.

Further research directions are associated to incorporating real-time data to the decisionmaking tool as well as broadening the spectrum of freight transportation problems and objectives to be taken into consideration, especially those related to environmental and sustainability issues. Further study may also involve political, infrastructural, and technological considerations given in freight distribution planning in any city.

Acknowledgements

We are grateful to the Gobernación del Departamento del Atlantico and the Sistema General de Regalias de la Republica de Colombia for having partially financed this work through Project LOGPORT, BPIN 20120001001911050672. FONDEF IT17M10012.

References

Reference

Ballou, R. H. (2004). Logística: administración de la cadena de suministro. https://books.google.com/books?hl=es&lr=&id=ii5xqLQ5VLgC&pgis=1

Bard, J. F., Kontoravdis, G., & Yu, G. (2002). A Branch-and-Cut Procedure for the Vehicle Routing Problem with Time Windows. Transportation Science, 36(2), 250-269. https://doi.org/10.1287/trsc.36.2.250.565

Bodin, L., Golden, B., Assad, A., & Ball, M. (1981). The state of the art in the routing and scheduling of vehicles and crews. https://trid.trb.org/view/171165

Cattaruzza, D., Absi, N., Feillet, D., & González-Feliu, J. (2017). Vehicle routing problems for city logistics. EURO Journal on Transportation and Logistics, 6(1), 51-79. https://doi.org/10.1007/s13676-014-0074-0

Chrissis, M. B., Konrad, M., & Shrum, S. (2011). CMMI ® Second Edition: Guidelines for Process Integration and Product Improvement. In SEI Series in Software Engineering. Pearson Education. https://doi.org/0321711505

Crainic, T. G., Errico, F., Rei, W., & Ricciardi, N. (2016). Modeling Demand Uncertainty in Two-Tier City Logistics Tactical Planning. Transportation Science, 50(2), 363-761. https://doi.org/10.1287/trsc.2015.0606

Dablanc, L. (2007). Goods transport in large European cities: Difficult to organize, difficult to modernize. Transportation Research Part A: Policy and Practice, 41(3), 280-285. https://doi.org/10.1016/J.TRA.2006.05.005

Gambardella, L., Taillard, É., & Agazzi, G. (1999). MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows. In New Ideas in Optimization (pp. 63-76.). McGraw-Hill's. https://doi.org/10.1.1.45.5381

Garcia-Najera, A., & Bullinaria, J. A. (2011). An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows. Computers & Operations Research, 38(1), 287-300. https://doi.org/io.ioi6/J.COR.20io.05.oo4

Gendreau, M., Guertin, F., Potvin, J.-Y., & Taillard, É. (1999). Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching. Transportation Science, 33(4), 381-390. https://doi.org/10.1287/trsc.334.381

Hesse, M., & Rodrigue, J.-P. (2004). The transport geography of logistics and freight distribution. Journal of Transport Geography, 12(3), 171-184. https://doi. org/10.1016/J.JTRANGEO.2003.12.o04

Holguín-Veras, J., Encarnación, T., González-Calderón, C. A., Winebrake, J., Kyle, S., Herazo-Padilla, N., Kalahasthi, L., Adarme, W., Cantillo, V., Yoshizaki, H., & Garrido, R. (2018). Direct impacts of off-hour deliveries on urban freight emissions. Transportation Research Part D: Transport and Environment, 61, 84-103. https://doi.org/10.1016/J.TRD.2016.10.013

Jacobson, I. (1992). Object-oriented software engineering : a use case driven approach. ACM Press.

Maropoulos, P. G., & Ceglarek, D. (2010). Design verification and validation in product lifecycle. CIRP Annals, 59(2), 740-759. https://doi.org/10.1016/J. CIRP.2010.05.005

Masrom, S., Abidin, S. Z. Z., Omar, N., Nasir, K., & Abd Rahman, A. S. (2015). Dynamic parameterization of the particle swarm optimization and genetic algorithm hybrids for vehicle routing problem with time window. International Journal of Hybrid Intelligent Systems, 12(1), 13-25. https://doi.org/10.3233/HIS-140202

Pecin, D., Contardo, C., Desaulniers, G., & Uchoa, E. (2017). New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows. INFORMS Journal on Computing, 29(3), 489-502. https://doi.org/10.1287/ijoc.2016.0744

Saeheaw, T., & Charoenchai, N. (2016). Comparison of Meta-heuristic Algorithms for Vehicle Routing Problem with Time Windows (pp. 1263-1273). Springer, Cham. https://doi.org/10.1007/978-3-319-24584-3_108

Sánchez-Dams, R. (2014). Metodología ágil estandarizada para el desarrollo o ejecución de proyectos de sistemas embebidos. Universidad del Norte.

Vigo, D., & Toth, P. (2014). Vehicle Routing; Problems, Methods, and Applications. In MOS-SIAM Series on Optimization. https://doi.org/doi:10.1137/1.9781611973594