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 fleet of vehicles. The optimizer within ORD uses a set of heuristics to create an efficient distribution plan. By taking into account traffic congestion, by including the time dependent travel times (TD-TTs) 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 TD-TTs 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 first research the accuracy of this TTC. Second, we develop a new approach which we call the Congestion Hierarchies Algorithm (CH-algorithm). Method: We measure the accuracy of the TTC using the BeNeLux road network, which contains the historical TD-TTs on the majority of the edges in the network. We take these historical travel times as the ground truth, and exclude any real-time information from this research. Since it is possible to compute TD-TTs 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 origin-destinations pairs (OD-pairs). All OD-pairs in a test set have characteristics like path length and geographical location. The CH-algorithm we developed is a TD-SP algorithm that uses multiple overlay levels to store precomputed congestion factors. The congestion factor is the delay percentage between the TD-TT and the free flow travel time (FF-TT) at a certain departure time. During optimization, the CH-algorithm calculates the TD-TTs by computing the FF-TT and multiplying it with the corresponding congestion factor. The method is fast as it only relies on a quick retrieval of the FF-TT, together with a table look-up and a multiplication. A quick FF-TT 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 benefit from a fine grid of areas, while remaining memory efficient, 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 fine 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 CH-algorithm wants to retrieve the congestion factors between an OD-pair, it will search the layers from bottom to top to find the layer in which both the origin and the destination node is in area, which have congestion factors between them precomputed. Results: The CH-algorithm outperforms the TTC in the majority of the experiments we ran. The results show that the CH-algorithm is on average 34% more accurate in congested areas, compared to the TTC. It also shows, that the CH-algorithm 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 sacrificed 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 4-hour trip (in free flow) 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 beneficial for the customer, as their distributions plans get more reliable. This means, less driver time violations, more on-time 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 benefits. 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: | https://purl.utwente.nl/essays/72040 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page