University of Twente Student Theses


Improving a Vehicle Routing Problem algorithm at Districon

Huizingh, Tom (2021) Improving a Vehicle Routing Problem algorithm at Districon.

[img] PDF
Abstract:Districon is one of the world’s leading consultancy firms when it comes to the area of supply chain and the application of analytics and decision support tools. Districon is located in Maarssen and has departments in the USA and Asia. Districon not only offers consultancy but also off-the-shelf IT solutions, interim project management, professionals and recruitment. A company denoted as ‘Company A’ requested Districon to come up with a solution to automate their routing scheduling activities. Company A is the pioneer in producing a food ingredient with more than 50 years of experience, the highest quality products at minimal costs are provided to the customer. Company A uses two huge production factories that are located in two different places. Furthermore, the produced ingredient is distributed by Company A over the depots that are divided over the regions in the country. The customers of Company A are mainly supermarkets and convenience stores. For the distribution of their products from the depots to the customers, Company A would like to have a Routing Planning Software (RPS) that produces high-quality routes in a relatively short computational time. Districon had already constructed a model in Python, from a former project, that is able to plan trips. This specific problem of Company A is denoted as a Heterogeneous Vehicle Routing Problem with Hard Time Windows (HVRPHTW). The problem is characterised as an NP-hard problem, implying that the optimal solution cannot be guaranteed within polynomial time. For this reason, Districon used a Tabu Search (TS) algorithm to find high quality (not optimal) solution in a relatively short time. However, the current model of Districon is constructed to solve Vehicle Routing Problems (VRPs) including homogeneous vehicles. Therefore, the goal of this research is to extend the current model such that it is able to solve a HVRPHTW. Literature has been conducted in order to learn more about the HVRPHTW. The algorithm proposed in the paper of Molina, Salmeron and Eguia (2020) has been used to extend the current model of Districon. Firstly, the current model was adapted such that it could handle heterogeneous vehicles and afterwards the algorithm of Molina, Salmeron and Eguia (2020) was implemented. This paper introduces a Variable Neighborhood Tabu Search (VNTS), the main notion behind this VNTS algorithm is that a local optimum for one neighborhood does not necessarily have to be a local optimum for another neighborhood. The new proposed algorithm consists of 3 phases: creation of the initial solution, improvement phase and the post optimization phase. The initial solution has been constructed by first allocating the customers random over the available vehicles and afterwards with help of the VNTS, the vehicles used in the solution will be minimized. This completes the initial solution and this initial solution will be improved by the VNTS in the improvement phase. This VNTS uses 6 different neighborhood structures: Relocate (inter- and intra-route), Exchange (inter- and intra-route), Cross-Exchange and the GENI-insertion. The algorithm terminates its search when 30 consecutive iterations without an improvement have been made. Subsequently, the best-found solution will be used as input solution for the post-optimization method. The post-optimization method attempts to split a route into two routes to evaluate if it is more cost-efficient to use two small vehicles instead of 1 big one. Finally, the VNTS will be applied once again to the output of the post-optimization method since new routes could be constructed by the post-optimization method which implements a new search area for the VNTS. In this way, the algorithm is able to tackle heterogeneous vehicle routing problems and make use of various different vehicles within a vehicle fleet. This VNTS algorithm was implemented in the model of Districon, experiments have been executed in order to set every parameter value of the algorithm. Examples of parameters are the termination criterium and the minimum and maximum length of the Tabu List. Subsequently, this new proposed algorithm has been compared against the current algorithm and it could be concluded that on average the newly proposed algorithm outperforms the current algorithm. The new algorithm outperforms the current algorithm on 16 out of 24 instances. On average the objective value is 7.1% lower and even the computational time is on average 382 seconds lower. Furthermore, the average truck capacity utilization is 0.95, while the current algorithm only has a truck capacity utilization of 0.89. However, in some cases the new proposed algorithm is struggling with the provided initial solution and is not able to find a feasible solution. Since the computational time is, in most cases, well within the 15 minutes this causes not always trouble. By implementing the new algorithm into the model, the requirements of Company and the goal of this thesis are fulfilled. The main recommendation to Districon is to conduct further research since the new algorithm has a high potential and due to the limited time in this research, it could not be fully exploited. Firstly, it is recommended to Districon to investigate why the VTNS is not able to find a feasible solution in a few cases or a new creation method for the initial solution could be constructed. Furthermore, to enlarge the search area of the algorithm, Districon should enable the algorithm to create and remove trips while iterating. Finally, it is recommended to extend this single depot model to a multi-depot model since Company A serves its customers from multiple depots. Besides, this extension could be used for future projects as well, since many companies that consult Districon have multiple depots.
Item Type:Essay (Bachelor)
Faculty:BMS: Behavioural, Management and Social Sciences
Subject:85 business administration, organizational science
Programme:Industrial Engineering and Management BSc (56994)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page