University of Twente Student Theses
Computing time dependent travel times in vehicle routing problems
Waegemakers, M.W.H. (2017) Computing time dependent travel times in vehicle routing problems.

PDF
8MB 
Abstract:  Motivation: One of the products delivered by ORTEC is a software suite called ORTEC Routing & Dispatch (ORD), which manages and optimizes the distribution process of delivering goods with a �eet of vehicles. The optimizer within ORD uses a set of heuristics to create an e�cient distribution plan. By taking into account tra�c congestion, by including the time dependent travel times (TDTTs) into the distribution plan, ORD improves the feasibility of the distribution plans and the overall solution quality by avoiding congested areas during rush hour. Currently, all exact algorithms that are able to compute the TDTTs are too slow to be used in optimization heuristics. To overcome this shortcoming, it is possible to approximate the TDTTs in favour of fast computations. ORD has the ability to use such an approximation algorithm, which we call the Travel Time Calculator (TTC). In this thesis, we �rst research the accuracy of this TTC. Second, we develop a new approach which we call the Congestion Hierarchies Algorithm (CHalgorithm). Method: We measure the accuracy of the TTC using the BeNeLux road network, which contains the historical TDTTs on the majority of the edges in the network. We take these historical travel times as the ground truth, and exclude any realtime information from this research. Since it is possible to compute TDTTs exactly, we are able to measure the loss of accuracy between the approximation algorithm and exact TDTTs. To research under which conditions the current approach becomes inaccurate, we create three test groups consisting of a total of 15 test sets of 2500 randomly selected origindestinations pairs (ODpairs). All ODpairs in a test set have characteristics like path length and geographical location. The CHalgorithm we developed is a TDSP algorithm that uses multiple overlay levels to store precomputed congestion factors. The congestion factor is the delay percentage between the TDTT and the free �ow travel time (FFTT) at a certain departure time. During optimization, the CHalgorithm calculates the TDTTs by computing the FFTT and multiplying it with the corresponding congestion factor. The method is fast as it only relies on a quick retrieval of the FFTT, together with a table lookup and a multiplication. A quick FFTT retrieval is possible using an algorithm like Highway Node Routing or Contraction Hierarchies. However, due to memory restrictions, simply storing all congestion factors is not an option. Therefore, we do not compute the congestion factors between each pair of singular nodes, but between areas of nodes. To bene�t from a �ne grid of areas, while remaining memory e�cient, we use multiple overlay layers that divide the road network into quadrants. Each layer is a quadratic subdivision of the layer above it. In the end, the lowest layer has �ne grid of many small areas, while the highest and second highest layer consist of only one and four areas, respectively. Only for the areas that are considered important enough, the algorithm will compute the congestion factors. If the CHalgorithm wants to retrieve the congestion factors between an ODpair, it will search the layers from bottom to top to �nd the layer in which both the origin and the destination node is in area, which have congestion factors between them precomputed. Results: The CHalgorithm outperforms the TTC in the majority of the experiments we ran. The results show that the CHalgorithm is on average 34% more accurate in congested areas, compared to the TTC. It also shows, that the CHalgorithm is on average 28% more accurate for trips with a length of at most 30 minutes, compared to the TTC. These values are weekday averages, during rush hour these values increase to 38% and 33% respectively. However, we decided while designing the algorithm that some accuracy for longer trips would be sacri�ced in favour of the shorter trips, resulting in an accuracy drop for trips longer than 30 minutes. The accuracy decreases on average with 85%, meaning that the average deviation increases from 1.7% to 2.7% and from 1.0% to 2.0% for trips of 2 hours and 4 hours respectively. To put this increase into perspective, the duration of a 4hour trip (in free �ow) on average has an additional deviation of 2.5 minutes. Recommendations: In this research, we present a proof of concept of the newly developed CHalgorithm. We showed promising results that could improve the feasibility of the vehicle routing solutions. This is bene�cial for the customer, as their distributions plans get more reliable. This means, less driver time violations, more ontime delivery, and ultimately less rescheduling and deployment of additional vehicles. This will eventually lead to a more reliable customer, which result in overall positive business bene�ts. Before this algorithm can be used, we recommend to further research the four preprocessing steps of the algorithm. We expect that there is still some potential accuracy to be gained. 
Item Type:  Essay (Master) 
Faculty:  ET: Engineering Technology 
Subject:  56 civil engineering 
Programme:  Civil Engineering and Management MSc (60026) 
Link to this item:  http://purl.utwente.nl/essays/72040 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page