Well-tuned algorithms for the Team Orienteering Problem with Time Windows

The Team Orienteering Problem with Time Windows (TOPTW) is the extension of the Orienteering Problem (OP) where each node is limited by a predefined time window during which the service has to start. The objective of the TOPTW is to maximize the total collected score by visiting a set of nodes with a limited number of paths. We propose two algorithms, Iterated Local Search and a hybridization of Simulated Annealing and Iterated Local Search (SAILS), to solve the TOPTW. As indicated in multiple research works on algorithms for the OP and its variants, determining appropriate parameter values in a statistical way remains a challenge. We apply Design of Experiments, namely factorial experimental design, to screen and rank all the parameters thereby allowing us to focus on the parameter search space of the important parameters. The proposed algorithms are tested on benchmark TOPTW instances. We demonstrate that well-tuned ILS and SAILS lead to improvements in terms of the quality of the solutions. More precisely, we are able to improve 50 best known solution values on the available benchmark instances.     

Ants can orienteer a thief in their robbery

The Thief Orienteering Problem (ThOP) is a multi-component problem that combines features of two classic combinatorial optimization problems: Orienteering Problem and Knapsack Problem. The ThOP is challenging due to the given time constraint and the interaction between its components. We propose an Ant Colony Optimization algorithm together with a new packing heuristic to deal individually and interactively with problem components. Our approach outperforms existing work on more than 90% of the benchmarking instances, with an average improvement of over 300%.     

The Clustered Orienteering Problem

In this paper we study a generalization of the Orienteering Problem (OP) which we call the Clustered Orienteering Problem (COP). The OP, also known as the Selective Traveling Salesman Problem, is a problem where a set of potential customers is given and a profit is associated with the service of each customer. A single vehicle is available to serve the customers. The objective is to find the vehicle route that maximizes the total collected profit in such a way that the duration of the route does not exceed a given threshold. In the COP, customers are grouped in clusters. A profit is associated with each cluster and is gained only if all customers belonging to the cluster are served. We propose two solution approaches for the COP: an exact and a heuristic one. The exact approach is a branch-and-cut while the heuristic approach is a tabu search. Computational results on a set of randomly generated instances are provided to show the efficiency and effectiveness of both approaches.     

Facets and valid inequalities for the time-dependent travelling salesman problem

The Time-Dependent Travelling Salesman Problem (TDTSP) is a generalization of the traditional TSP where the travel cost between two cities depends on the moment of the day the arc is travelled. In this paper, we focus on the case where the travel time between two cities depends not only on the distance between them, but also on the position of the arc in the tour. We consider two formulations proposed in the literature, we analyze the relationship between them and derive several families of valid inequalities and facets. In addition to their theoretical properties, they prove to be very effective in the context of a Branch and Cut algorithm.     

Metaheuristics for the team orienteering problem

The Team Orienteering Problem (TOP) is the generalization to the case of multiple tours of the Orienteering Problem, known also as Selective Traveling Salesman Problem. A set of potential customers is available and a profit is collected from the visit to each customer. A fleet of vehicles is available to visit the customers, within a given time limit. The profit of a customer can be collected by one vehicle at most. The objective is to identify the customers which maximize the total collected profit while satisfying the given time limit for each vehicle. We propose two variants of a generalized tabu search algorithm and a variable neighborhood search algorithm for the solution of the TOP and show that each of these algorithms beats the already known heuristics. Computational experiments are made on standard instances.     

Solving the Probabilistic TSP with Ant Colony Optimization

In this paper, we describe new ways to apply Ant Colony Optimization (ACO) to the Probabilistic Traveling Salesperson Problem (PTSP). PTSP is a stochastic extension of the well known Traveling Salesperson Problem (TSP), where each customer will require a visit only with a certain probability. The goal is to find an a priori tour visiting all customers with minimum expected length, customers not requiring a visit simply being skipped in the tour.We show that ACO works well even when only an approximative evaluation function is used, which speeds up the algorithm, leaving more time for the actual construction. As we demonstrate, this idea can also be applied successfully to other state-of-the-art heuristics. Furthermore, we present new heuristic guidance schemes for ACO, better adapted to the PTSP than what has been used previously. We show that these modifications lead to significant improvements over the standard ACO algorithm, and that the resulting ACO is at least competitive to other state-of-the-art heuristics.     

An effective PSO-inspired algorithm for the team orienteering problem

The Team Orienteering Problem (TOP) is a particular vehicle routing problem in which the aim is to maximize the profit gained from visiting customers without exceeding a travel cost/time limit. This paper proposes a new and fast evaluation process for TOP based on an interval graph model and a Particle Swarm Optimization inspired Algorithm (PSOiA) to solve the problem. Experiments conducted on the standard benchmark of TOP clearly show that our algorithm outperforms the existing solving methods. PSOiA reached a relative error of 0.0005% whereas the best known relative error in the literature is 0.0394%. Our algorithm detects all but one of the best known solutions. Moreover, a strict improvement was found for one instance of the benchmark and a new set of larger instances was introduced.     

A novel GRASP solution approach for the Orienteering Problem

The Orienteering Problem (OP) is a well-known variant of the Traveling Salesman Problem. In this paper, a novel Greedy Randomized Adaptive Search Procedure (GRASP) solution is proposed to solve the OP. The proposed method is shown to outperform state-of-the-art heuristics for the OP in producing high quality solutions. In comparison with the best known solutions of standard benchmark instances, the method can find the optimal or the best known solution of about 70 % of the instances in a reasonable time, which is about 17 % better than the best known approach in the literature. Moreover, a significant improvement is achieved on the solution of two standard benchmark instances.     

An Insert/Delete Heuristic for the Travelling Salesman Subset-Tour Problem with One Additional Constraint

The Travelling Salesman Subset-tour Problem (TSSP) differs from the well-known Travelling Salesman Problem (TSP) in that the salesman is not required to visit every city. Many problems, such as the prize collecting TSP, the orienteering problem, and the time constrained TSP, can be viewed as TSSPs with one additional constraint (TSSP + 1). In this paper, we present a heuristic approach for the TSSP + I class of problems. The general philosophy of our approach is to maintain tour feasibility with respect to the TSSP subproblem. This allows us to begin our approach with any TSSP tour. In each step, the insertion or deletion of a city is performed either to reduce infeasibility in the additional constraint or to improve upon the minimization objective. We present computational results that show our approach is superior to approaches using just insertion, and thus demonstrate the importance of considering the possible deletion of cities.     

A General Vehicle Routing Problem

In this paper, we study a rich vehicle routing problem incorporating various complexities found in real-life applications. The General Vehicle Routing Problem (GVRP) is a combined load acceptance and generalised vehicle routing problem. Among the real-life requirements are time window restrictions, a heterogeneous vehicle fleet with different travel times, travel costs and capacity, multi-dimensional capacity constraints, order/vehicle compatibility constraints, orders with multiple pickup, delivery and service locations, different start and end locations for vehicles, and route restrictions for vehicles. The GVRP is highly constrained and the search space is likely to contain many solutions such that it is impossible to go from one solution to another using a single neighbourhood structure. Therefore, we propose iterative improvement approaches based on the idea of changing the neighbourhood structure during the search.     

A priori orienteering with time windows and stochastic wait times at customers

In the pharmaceutical industry, sales representatives visit doctors to inform them of their products and encourage them to become an active prescriber. On a daily basis, pharmaceutical sales representatives must decide which doctors to visit and the order to visit them. This situation motivates a problem we more generally refer to as a stochastic orienteering problem with time windows (SOPTW), in which a time window is associated with each customer and an uncertain wait time at a customer results from a queue of competing sales representatives. We develop a priori routes with the objective of maximizing expected sales. We operationalize the sales representative’s execution of the a priori route with relevant recourse actions and derive an analytical formula to compute the expected sales from an a priori tour. We tailor a variable neighborhood search heuristic to solve the problem. We demonstrate the value of modeling uncertainty by comparing the solutions to our model to solutions of a deterministic version using expected values of the associated random variables. We also compute an empirical upper bound on our solutions by solving deterministic instances corresponding to perfect information.     

Optimal solutions for routing problems with profits

In this paper, we present a branch-and-price algorithm to solve two well-known vehicle routing problems with profits, the Capacitated Team Orienteering Problem and the Capacitated Profitable Tour Problem. A restricted master heuristic is applied at each node of the branch-and-bound tree in order to obtain primal bound values. In spite of its simplicity, the heuristic computes high quality solutions. Several unsolved benchmark instances have been solved to optimality.     

Scatter Search and Bionomic Algorithms for the aircraft landing problem

The problem of deciding how to land aircraft approaching an airport involves assigning each aircraft to an appropriate runway, computing a landing sequence for each runway and scheduling the landing time for each aircraft. Runway allocation, sequencing and scheduling for each aircraft must ensure the scheduled landing time lies within a predefined time window and meet separation time requirements with other aircraft. The objective is to achieve effective runway use.In this paper, the multiple runway case of the static Aircraft Landing Problem is considered. Two heuristic techniques are presented: Scatter Search and the Bionomic Algorithm, population heuristic approaches that have not been applied to this problem before.Computational results are presented for publicly available test problems involving up to 500 aircraft and five runways showing that feasible solutions of good quality can be produced relatively quickly.     

The time-dependent capacitated profitable tour problem with time windows and precedence constraints

We introduce the time-dependent capacitated profitable tour problem with time windows and precedence constraints. This problem concerns determining a tour and its departure time at the depot that maximizes the collected profit minus the total travel cost (measured by total travel time). To deal with road congestion, travel times are considered to be time-dependent. We develop a tailored labeling algorithm to find the optimal tour. Furthermore, we introduce dominance criteria to discard unpromising labels. Our computational results demonstrate that the algorithm is capable of solving instances with up to 150 locations (75 pickup and delivery requests) to optimality. Additionally, we present a restricted dynamic programing heuristic to improve the computation time. This heuristic does not guarantee optimality, but is able to find the optimal solution for 32 instances out of the 34 instances.     

Heuristics for the Stochastic Eulerian Tour Problem

The Stochastic Eulerian Tour Problem (SETP) seeks the Eulerian tour of minimum expected length on an undirected Eulerian graph, when demand on the arcs that have to be serviced is probabilistic. The SETP is NP-hard and in this paper, we develop three constructive heuristics for this problem. The first two are greedy tour construction heuristics while the third is a sub-tour concatenation heuristic. Our experimental results show that for grid networks, the sub-tour concatenation heuristic performs well when the probability of service of each edge is greater than 0.1. For Euclidean networks, as the number of edges increases, the second heuristic performs the best among the three. Also, the expected length of our overall best solution is lower than the expected length of a random tour by up to 10% on average for grid networks and up to 2% for Euclidean networks.     

A two-stage solution approach for the Directed Rural Postman Problem with Turn Penalties

In this paper, we consider the Directed Rural Postman Problem with Turn Penalties (DRPP-TP). A solution is a tour that traverses all required arcs of the graph. The total cost of the tour is the sum of the lengths of the traversed arcs plus the penalties associated with the turns. One solution approach involves transforming the arc routing problem into an equivalent node routing problem. An alternative direct approach (without graph transformation) that involves two stages has been proposed in the literature. In the first part of this paper, we investigate the applicability of the direct approach. We identify several characteristics of the input instance that make this approach effective and present several limitations of this approach. In the second part of this paper, we describe an integer linear program that is combined with a local search algorithm. This combination produces high-quality solutions to the DRPP-TP in a reasonable amount of computing time.     

Advanced routing for city logistics service providers based on time-dependent travel times

Increasing traffic demand, recurring congestion and sophisticated e-commerce business models lead to enormous challenges for routing in city logistics. We introduce a planning system for city logistics service providers, which faces those challenges by more realistic vehicle routing considering time-dependent travel times. Time-dependent travel times arise from telematics-based traffic data collection city-wide. Well-known heuristics for the Traveling Salesman Problem and for the Vehicle Routing Problem are adapted to time-dependent planning data. Computational experiments allow for insights into the efficiency of individual heuristics, their adaptability to time-dependent planning data sets, and the quality and structure of resulting delivery tours.     

Rendezvous search on the line with bounded resources: expected time minimization

Two players are placed on the line and want to meet. Neither knows the direction of the other, but they know the distance between them or perhaps the distribution of this distance. They can move with speed at most one, and each has a ‘resource constraint’ on the total distance he can travel. We first consider the question of whether the two players can ensure that they meet. When they can, then we seek the least expected meeting time. Otherwise, we maximize the probability of a meeting.This generalizes the similar problem studied by the first author and S. Gal [SIAM J. Control and Optimization 33/4 (1995) 1270] without any resource constraint, and indeed for sufficiently large resources gives the same rendezvous time, i.e. least expected time to meet. The paper may also be considered a generalization of the Linear Search Problem, studied by the second author and others, which corresponds to the case when one of the resource constraints is zero, so that player cannot move. More specifically, it generlaizes the bounded resource version of the Linear Search Problem presented by Foley, Hill and Spruill [Naval Research Logistics 38 (1991) 555–565].     

Stochastic optimization of an urban rail timetable under time‐dependent and uncertain demand

Urban rail planning is extremely complex, mainly because it is a decision problem under different uncertainties. In practice, travel demand is generally uncertain, and therefore, the timetabling decisions must be based on accurate estimation. This research addresses the optimization of train timetable at public transit terminals of an urban rail in a stochastic setting. To cope with stochastic fluctuation of arrival rates, a two‐stage stochastic programming model is developed. The objective is to construct a daily train schedule that minimizes the expected waiting time of passengers. Due to the high computational cost of evaluating the expected value objective, the sample average approximation method is applied. The method provided statistical estimations of the optimality gap as well as lower and upper bounds and the associated confidence intervals. Numerical experiments are performed to evaluate the performance of the proposed model and the solution method.     

Ambulance location and relocation problems with time-dependent travel times

EMERGENCY SERVICE PROVIDERS ARE FACING THE FOLLOWING PROBLEM: how and where to locate vehicles in order to cover potential future demand effectively. Ambulances are supposed to be located at designated locations such that in case of an emergency the patients can be reached in a time-efficient manner. A patient is said to be covered by a vehicle if (s)he can be reached by an ambulance within a predefined time limit. Due to variations in speed and the resulting travel times it is not sufficient to solve the static ambulance location problem once using fixed average travel times, as the coverage areas themselves change throughout the day. Hence we developed a multi-period version, taking into account time-varying coverage areas, where we allow vehicles to be repositioned in order to maintain a certain coverage standard throughout the planning horizon. We have formulated a mixed integer program for the problem at hand, which tries to optimize coverage at various points in time simultaneously. The problem is solved metaheuristically using variable neighborhood search. We show that it is essential to consider time-dependent variations in travel times and coverage respectively. When ignoring them the resulting objective will be overestimated by more than 24%. By taking into account these variations explicitly the solution on average can be improved by more than 10%.