Problem setting

Within the domain of operations research, vehicle routing problems (VRP) focus on determining an optimal route to visit all customers using a fleet of vehicles, each constrained by a load capacity or a travel time. Managing such a fleet of vehicles is a challenging but a crucial task for companies distributing goods to customers. They need to determine the best order to visit the customers and how to assign the customers to the available vehicles. Moreover, they have to take into account congestion issues: the travel time between two customers will vary significantly during the day. This means that the drivers of the vehicles should try to avoid the busiest areas and roads during rush hour. The orienteering problem (OP) differs from this classic VRP as not all customers can be visited due to a limited time budget, instead a selection of the most profitable ones needs to be made. The OP and its variants have recently received a lot of attention in the literature. A recent trend is the incorporation of timedependent travel times. Such problems are more realistic, because they account for travel time variability, which is overwhelmingly present in real life. However, the number of publications about the time-dependent orienteering problem (TDOP) but also the time-dependent VRP (TD-VRP) is tiny compared to the number of scientific publications about other extensions of both the OP and the VRP. This lack of research interest is unfortunate, since congestion and thus time-dependent travel times cannot be ignored in a lot of practical applications. The main aim of this dissertation is therefore to develop efficient solution methods to deal with various types of time-dependent orienteering problems within a short computation time.

Problems descriptions

The orienteering problem (OP) is defined on a graph in which the vertices represent customers where a reward can be collected. An arc in the graph represents a connection between two vertices and has a certain travel time. The goal of the OP is to determine which subset of vertices to visit and in which order so that the total collected reward is maximized and a given maximum total travel time is not exceeded. In addition to this, a feasible OP solution should start and end at a predetermined vertex. The OP can be extended with a time window and a service time attached to each vertex. The service time represents the time necessary to serve a vertex and the time window stands for the opening and closing time of a vertex. Congestion is modelled by making various assumptions about the travel time required to traverse an arc. If the travel time is a fixed value it is defined as being deterministic. If this travel time is not a fixed value but the value is subject to variations, the travel time is said to be stochastic. On the other hand, a distinction has to be made between time-independent and time-dependent travel times. If the time to traverse an arc is not dependent on the hour of the day, it is considered to be time-independent and can be represented as a single value. When the travel time is different on different moments of the day, the travel time is said to be time-dependent. The orienteering problem with time-dependent and deterministic travel time information is called the time-dependent orienteering problem (TDOP). Recall that in this case, the travel time on an arc depends on the hour of the day the arc is taken. Therefore, it can no longer be seen as a single value but as a function of values dependent on the departure time. The TD-OP and its extension with time-windows (TD-OPTW) will be discussed in this dissertation. The variant of the orienteering problem where the travel time is both stochastic and time-dependent is called the time-dependent orienteering problem with stochastic weights (TD-OPSW). Its extension with time windows, called the time-dependent orienteering problem with stochastic weights and time windows or TD-OPSWTW, will also be discussed in this dissertation. A travel time at a certain hour of the day is now represented by a probability distribution instead of by a single value. So the travel time is represented by different probability distributions depending on the departure time. Moreover, realistic time-dependent test instances for TD-OP with known optimal solutions are developed, based on the original time-independent OP instances in combination with a well performing speed model for the TD-VRP. For the TDOPTW and the TD-OPSWTW a set of realistic problem instances was developed, based on the road network of the Benelux (Belgium, The Netherlands and Luxembourg) which contains 425,479 vertices and 519,915 arcs. The historical travel time dataset, consisting of accurately recorded travel time observations every 15 minutes for a representative Tuesday, is used to calculate the travel time function and travel time distributions for each arc.

Solution approach

Since high-quality solutions are required and the computation time should be limited to only a few seconds for instances of realistic size, the literature on vehicle routing suggests the implementation of a metaheuristic. These solution methods try to find better solutions combining efficient local search moves with diversification mechanisms. Local search moves try to improve an existing solution by making small changes to the current solution. The main contribution of this dissertation, apart from a mathematical formulation for the three proposed problems (TD-OP, TD-OPTW, TD-OPSWTW), are several fast local search based metaheuristics inspired by an ant colony system (ACS). The ACS is based on the behaviour of a foraging ant colony, using ethereal pheromone trails to mark travelled arcs. The ACS starts by sequentially creating a number of initial solutions. The construction process starts from the first vertex and in succession adds a new vertex to the solution based on greedy information and pheromone trails of the arcs leading to that vertex. The greedy information is based on a ratio which consists of the reward of a vertex and the distance towards a vertex. After the creation of a complete solution, the included arcs are made less attractive for subsequent construction procedures, in order to increase diversification. This is done by depreciating the pheromone values with an evaporation rate factor (local pheromone update). Once all solutions of one iteration are created, they are improved, using a different set of local search moves for each problem. The solution with the highest total reward of this iteration is stored. Finally, the arcs that are used in this solution are made more attractive to be used in the solution construction procedure of succeeding iterations, by increasing their corresponding pheromone value. These steps are repeated during a specified number of iterations and the best solution over all iterations is stored. To prevent that only a couple of arcs dominate this solution construction procedure, the pheromone values are reset during a global pheromone update when no improvement can be found during a certain number of iterations. For the TD-OP, the set of local search moves consists of a modified 2-opt move and a time-dependent insert move. The modified 2-opt move first preselects interesting arcs based on the gain in distance. The most interesting arc pair is then evaluated based on real travel times. If the new solution is feasible, it is accepted. The insert move is sped up by a local evaluation metric. This local evaluation metric prevents a full and time-consuming evaluation of a solution after every modification attempt and enables an efficient checking and updating mechanism. Therefore, we store for every vertex in the current solution the maximum amount of time that a visit to it can be postponed before the solution becomes infeasible. For the TD-OPTW, three time-dependent local search moves have been implemented. Firstly, the insert move and local evaluation metric were adapted to account for time windows. Secondly, a time-dependent replace move tries to replace a vertex from the current solution with a non included vertex with a higher reward. Thirdly, a swap local search move tries to exchange two solution member vertices in order to save travel time. For the TD-OPSWTW, the combination of time-dependency, time windows and stochastic travel time severely complicates the calculation of the departure and arrival time distributions. Therefore, three prominent complications were defined in this dissertation and the way they were dealt with by the proposed estimation algorithm is explained and might also be useful for other vehicle routing problems with time windows and time-dependent stochastic travel times. In addition to this stochastic ant colony system (SACS), three stochastic local search moves are used, namely a stochastic swap local search move and a stochastic insert and a replace local search move.

Results

The proposed algorithm for the TD-OP obtains high-quality results on the developed instances requiring very small computation times, even for instances with around 100 vertices. An average run obtains solutions with a reward gap with the optimal solution of only 1.4% using 0.5 seconds of computation time. For 44% of the test instances, the known optimal solution is found. A sensitivity analysis demonstrates that the performance of the algorithm is not sensitive to small changes in the parameter settings. The TD-OPTW algorithm obtains very good results on the benchmark instances, requiring small computation times due to the combination of a well performing metaheuristic framework and the interaction effect between three efficient local search moves, tailored towards the problem characteristics. The average reward gap with the known optimal solution on these test instances is only 0.2% with an average computation time of 0.4 seconds. A comparison between the ACS and a state-of-the-art technique showed that the performance of this state-of-theart technique is 6.2% worse. Finally, the optimal OPTW solutions, ignoring the time-dependency of the arcs in the TD-OPTW, perform on average at least 11.4% worse than the proposed ACS solutions. A TD-OPTW solution differs on average 35.6% from an optimal OPTW solution sequence. Concerning the TD-OPSWTW, promising results were obtained in a reasonable amount of computation time. A first comparison is made by comparing the results of the SACS with optimal solutions for the regular OP with time windows, found using an exact solution method, that are evaluated in a stochastic environment. The solutions proposed by the SACS are on average 23.8% better than executing the optimal solution sequence in a time-dependent stochastic environment. Secondly, the solutions generated by the ACS for TD-OPTW, using different percentiles of the travel time distribution as input, were also evaluated in a stochastic environment and compared to the solutions of the SACS. The SACS performs better than the ACS, independent of the used travel time percentile, as it takes into account the stochastic nature of this problem. However, the SACS also requires a greater computation time. Thirdly, when solving the certainty equivalence problem using the ACS method for the TD-OPTW, the SACS improves solutions by 1.3% on average. When solving the certainty equivalence problem the mean of the stochastic travel time is taken as travel time estimate. The fourth observation is the solution sequence being on average 28.3% different, compared to the proposed solution by the state-of-the-art algorithm. Subsequently, a surprising practical insight is that a probable late arrival at a vertex can either increase or decrease the standard deviation of the departure time. When it is 100% certain that a vertex is visited on time, its standard deviation of the departure time is equal to the standard deviation of its arrival time. The probability of arriving early at a vertex decreases the standard deviation of the departure time. The effect of a probable late arrival depends among other things on the ratio of the standard deviation of the arrival time and the length of the service time. In general, at the beginning of the solution sequence the service time is likely to be higher than the standard deviation of the arrival time as the service time comprises usually several minutes while the standard deviation of the arrival time is equal to zero at that point. However, the standard deviation of the arrival time tends to increase towards the end of the solution sequence. In short, a probability of a late arrival in the beginning of the solution sequence increases the standard deviation of the arrival time whereas a probable late arrival at the end of the solution sequence might decrease the standard deviation of the arrival time. The combination of these results should motivate vehicle trip planners to consider the time-dependent and stochastic nature of the travel times in the future.

Practical application

Apart from the theoretical problem instances, the acquired insights and solution concepts are also applied on a practical case. In this application, the data from two logistics companies, is used to design vehicle routing planning schedules respectively in Belgium and The Netherlands. Additional practical requirements are modelled such as different time windows per day, the use of multiple vehicles, a lunch break and capacity limitations. The solution method for TD-OPTW was adapted as some of these requirements drastically change the way a solution can be evaluated and altered by the local search moves. From this real-life application, we conclude that it pays off to take time-dependency into account during the optimization process. Increasing the performance of the algorithm and considering a multi-objective between route related costs and time-dependent travel times offers the main avenue for further research.

Conclusion

Orienteering problems with time-dependent and stochastic travel times are complex problems that require efficient solution methods to avoid a time consuming evaluation when a small change is made to a solution. These problems can be applied to vehicle routing applications that suffer from congestion. As in a realistic road network the travel time is dependent on the hour of the day due to traffic congestion. On top of that, many factors cause that one can never be sure when to arrive precisely at the destination. In this dissertation, several solution methods are presented that are able to solve these kind of problems in an efficient way. The solution methods are tested on realistic test problems and one of them is also applied to a real life logistic case study.