Search

The Traveling Salesman Problem with a Drone (TSP-D) is a hybrid truck and drone model of delivery, in which the drone rides on the truck and launches from the truck to deliver packages. Our approach to the TSP-D uses branch and bound, whereby each node of the branch-and-bound tree corresponds with a potential order to deliver a subset of packages. An approximate lower bound at each node is given by solving a dynamic program. We provide additional variants of our heuristic approach and compare solution quality and computation times. Consideration is given to various input parameters and distance metrics. The online supplement is available at https://doi.org/10.1287/ijoc.2018.0826 .

We construct empirically based regression models for estimating the tour length in the Close Enough Traveling Salesman Problem (CETSP). In the CETSP, a customer is considered visited when the salesman visits any point in the customer’s service region. We build our models using as many as 14 independent variables on a set of 780 benchmark instances of the CETSP and compare the estimated tour lengths to the results from a Steiner zone heuristic. We validate our results on a new set of 234 instances that are similar to the 780 benchmark instances. We also generate results for a new set of 72 larger instances. Overall, our models fit the data well and do a very good job of estimating the tour length. In addition, we show that our modeling approach can be used to accurately estimate the optimal tour lengths for the CETSP.

Local governments inspect roads to decide which segments and intersections to repair. Videos are taken using a camera mounted on a vehicle. The vehicle taking the videos proceeds straight or takes a left turn to cover an intersection fully. We introduce the intersection inspection rural postman problem (IIRPP), which is a new variant of the rural postman problem (RPP) that involves turns. We develop integer programming formulations of the IIRPP based on two different graph transformations to generate least-cost vehicle routes. One formulation is based on a new idea of transforming a graph. A second formulation is based on a graph transformation idea from the literature. Computational experiments show that the formulation involving the new graph transformation idea performs much better than the other formulation. We also develop an RPP-based heuristic and a heuristic based on a modified RPP. Heuristic solutions are improved by solving integer programming formulations on an induced subgraph. Computational experiments show that the heuristics based on the modified RPP perform much better than the RPP-based heuristics. The best-performing heuristic generates very good quality IIRPP-feasible routes on large street networks quickly. Summary of Contribution. Our paper addresses a real-world problem faced by local governments during road inspections. The real-world problem that we solve and the methodologies that we use fall at the intersection of computing and operations research. We introduce the intersection inspection rural postman problem, which is a new variant of the rural postman problem that involves turns to capture this real-world scenario. The rural postman problem is an important problem in vehicle routing. Studying new variants of this problem is key to extending the practice and theory of vehicle routing. We develop an integer programming formulation based on a new idea of transforming a graph and also develop heuristics based on the rural postman problem.

This paper addresses a variant of the Traveling Salesman Problem (TSP) known as the Close-Enough Traveling Salesman Problem (CETSP). A salesman does not have to visit the exact location of each customer. Instead, the salesman needs only to get close enough to each customer. This feature allows savings from the classic TSP solution, but also adds complexity to the problem. We develop a Steiner Zone Variable Neighborhood Search heuristic (SZVNS) to solve the CETSP. We conduct computational experiments on 842 instances. SZVNS often produces optimal solutions to the small instances where optimal solutions are known. On the larger instances, SZVNS produces shorter or similar solutions in less time when compared to the solutions produced by state-of-the-art heuristics.

In arc routing applications, some streets may require service along both sides of the street. For a subset of these streets, the vehicle operator may choose to service both sides during a single traversal. We refer to this as zigzag service. In contrast to servicing each side separately, the vehicle stops more frequently and incurs a traversal cost, two service costs, and a penalty cost associated with the slowed travel time required to perform the zigzag service. The tradeoff is that the vehicle only needs to service the street once on its route. However, for other streets zigzag service is only possible during the early part of a day when there is very little traffic. This scenario is modeled by the Windy Rural Postman Problem with Zigzag Time Windows (WRPPZTW). We develop a hybrid heuristic for the WRPPZTW that combines standard insertion and local search techniques with integer programming. We compare the computational performance of our heuristic to an exact procedure from Nossack et al. (2017) on a set of small instances with 28 edges and test the scalability of our heuristic on a set of larger grid instances with as many as 1200 edges.

In practice, it is often desirable for the routes of vehicles to be compact and separate. A set of routes is compact if the streets serviced by each route are geographically clustered, and separated if the routes overlap minimally. We consider the Min-Max K Windy Rural Postman Problem MMKWRPP, in which the objective is to route a homogeneous fleet of K vehicles such that the cost of the longest route is minimized. We develop a heuristic that is algorithmically simple, produces solutions that are comparable in quality to those produced by an existing approach, and performs well with respect to metrics that quantify compactness and separation. Our heuristic uses a partitioning scheme in which the weight of a vertex includes contributions from both incident streets requiring service and the distance needed to travel to a vertex. We present computational results for a set of instances that we generate from real-world street networks and for a set of artificial instances. Our code is part of the Open-source Arc Routing Library OAR Lib at https://github.com/Olibear/ArcRoutingLibrary. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 693, 290-303 2017

The min-max Split Delivery Multi-Depot Vehicle Routing Problem with Minimum Service Time Requirement (min-max SDMDVRP-MSTR) is a variant of the Multi-Depot Vehicle Routing Problem. Each customer requires a specified amount of service time. The service time can be split among vehicles as long as each vehicle spends a minimum amount of service time at a customer. The objective is to minimize the duration of the longest route (where duration is the sum of travel and service times).We develop a heuristic (denoted by MDS) that solves the min-max SDMDVRP-MSTR in three stages: (1) initialize a feasible solution without splits; (2) improve the longest routes by splitting service times; (3) ensure all minimum service time requirements are satisfied. The first stage of MDS is compared to an existing heuristic to solve the min-max Multi-Depot Vehicle Routing Problem on 43 benchmark instances. MDS produces 37 best-known solutions. We also demonstrate the effectiveness of MDS on 21 new instances whose (near) optimal solutions can be estimated based on geometry. Finally, we investigate the savings from split service and the split patterns as we vary the required service times, the average number of customers per route, and the minimum service time requirement. HighlightsA new variant of the Multiple Depot Vehicle Routing Problem is described.We develop a heuristic that generates high-quality solutions to benchmark and new instances.Our heuristic could be used by managers in applications such as newspaper delivery and disaster relief routing.

The split delivery vehicle routing problem (SDVRP) is a relaxed version of the classic capacitated vehicle routing problem (CVRP). Customer demands are allowed to split among vehicles. This problem is computationally challenging and the state-of-the-art heuristics are often complicated to describe and difficult to implement, and usually have long computing times. All these hinder their application by practitioners to solve real-world problems. We propose a novel, efficient, and easily implemented approach to solve the SDVRP using an a priori split strategy, that is, each customer demand is split into small pieces in advance. Our computational experiments on 82 benchmark instances show that our algorithm is overall much more efficient and produces results that are comparable to those from the state-of-the-art approaches.

In the multi-depot vehicle routing problem (MDVRP), there are several depots where vehicles can start and end their routes. The objective is to minimize the total distance travelled by all vehicles across all depots. The min-max multi-depot vehicle routing problem (Min-Max MDVRP) is a variant of the standard MDVRP. The primary objective is to minimize the length of the longest route. We develop a heuristic (denoted by MD) for the Min-Max MDVRP that has three stages: (1) simplify the multi-depot problem into a single depot problem and solve the simplified problem; (2) improve the maximal route; (3) improve all routes by exchanging customers between routes. MD is compared with two alternative heuristics that we also develop and an existing method from the literature on a set of 20 test instances. MD produces 15 best solutions and is the top performer. Additional computational experiments on instances with uniform and non-uniform distributions of customers and varying customer-to-vehicle ratios and with real-world data further demonstrate MD’s effectiveness in producing high-quality results.

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.

In winter, a common problem is to determine a set of routes for snow plows that minimize the maximum route length. Typically, this is modelled as an arc routing problem. We begin with a variant that is motivated by the fact that deadhead travel over streets is significantly faster than the time it takes to plow the street. We incorporate the use of multiple plows and the observation that, on steep streets, it is much more difficult, or impossible, to plow uphill. Therefore, we want to design routes that try to avoid plowing uphill on steep streets and take advantage of the faster traversal time for deadheading. We generalize this problem to include multiple plows and seek to minimize the maximum route length. We present a heuristic that generates solutions with costs that are very close to a lower bound.

In winter, a common problem is to determine the route that a snowplow should take in order to minimize the distance traveled. We propose a variant of this arc routing problem that is motivated by the fact that deadhead travel over streets that have already been plowed is significantly faster than the time it takes to plow the street. This problem differs from most arc routing problems because the cost of traversing a street changes depending on the order of the streets on a route. We develop a method that generates near-optimal solutions to instances as large as 200 nodes.

In the vehicle routing problem (VRP), a fleet of vehicles must service the demands of customers in a least-cost way. In the split delivery vehicle routing problem (SDVRP), multiple vehicles can service the same customer by splitting the deliveries. By allowing split deliveries, savings in travel costs of up to 50 % are possible, and this bound is tight. Recently, a variant of the SDVRP, the split delivery vehicle routing problem with minimum delivery amounts (SDVRP-MDA), has been introduced. In the SDVRP-MDA, split deliveries are allowed only if at least a minimum fraction of a customer’s demand is delivered by each visiting vehicle. We perform a worst-case analysis on the SDVRP-MDA to determine tight bounds on the maximum possible savings.

The distribution of relief aid is a complex problem where the operations have to be managed efficiently due to limited resources. We present a routing problem for relief operations whose primary goal is to satisfy demand for relief supplies at many locations taking into account the urgency of each demand. We have a single vehicle of unlimited capacity. Each node (location) has a demand and a priority. The priority indicates the urgency of the demand. Typically, nodes with the highest priorities need to be visited before lower priority nodes. We describe a new and interesting model for humanitarian relief routing that we call the hierarchical traveling salesman problem (HTSP). We compare the HTSP and the classical TSP in terms of worst-case behavior. We obtain a simple, but elegant result that exhibits the fundamental tradeoff between efficiency (distance) and priority and we provide several related observations and theorems.

The multi-depot split delivery vehicle routing problem combines the split delivery vehicle routing problem and the multiple depot vehicle routing problem. We define this new problem and develop an integer programming-based heuristic for it. We apply our heuristic to 30 instances to determine the reduction in distance traveled that can be achieved by allowing split deliveries among vehicles based at the same depot and vehicles based at different depots. We generate new test instances with high-quality, visually estimated solutions and report results on these instances.

We develop a heuristic for the period vehicle routing problem that uses an integer program and the record-to-record travel algorithm. Our heuristic produces very high-quality results on standard benchmark instances. We extend our heuristic to handle real-world routing considerations that involve reassigning customers to new routes and balancing the workload among drivers across routes. We demonstrate how these new variants can be used by managers to generate effective routes in practice.

The vehicle routing problem (VRP) is a difficult and well-studied combinatorial optimization problem. We develop a parallel algorithm for the VRP that combines a heuristic local search improvement procedure with integer programming. We run our parallel algorithm with as many as 129 processors and are able to quickly find high-quality solutions to standard benchmark problems. We assess the impact of parallelism by analyzing our procedure's performance under a number of different scenarios.

In the vehicle routing problem, a fleet of vehicles must service the demands of customers in a least-cost way. By allowing multiple vehicles to service the same customer (i.e., splitting deliveries), substantial savings in travel costs are possible. However, split deliveries are often an inconvenience to the customer who would prefer to have demand serviced in a single visit. We consider the vehicle routing problem in which split deliveries are allowed only if a minimum fraction of a customer’s demand is serviced by a vehicle. We develop a heuristic method for solving this problem and report computational results on a wide range of problem sets.

We present an approach based on linear programming (LP) that estimates the weights for a pairwise comparison matrix generated within the framework of the analytic hierarchy process. Our approach makes sense for a number of reasons, which we discuss. We apply our LP approach to several sample problems and compare our results to those produced by other, widely used methods. In addition, we extend our linear program to include applications where the pairwise comparison matrix is constructed from interval judgments.

The standard vehicle routing problem was introduced in the OR/MS literature about 45 years ago. Since then, the vehicle routing problem has attracted an enormous amount of research attention. In the late 1990s, large vehicle routing problem instances with nearly 500 customers were generated and solved using metaheuristics. In this paper, we focus on very large vehicle routing problems. Our contributions are threefold. First, we present problem instances with as many as 1200 customers along with estimated solutions. Second, we introduce the variable-length neighbor list as a tool to reduce the number of unproductive computations. Third, we apply record-to-record travel with a variable-length neighbor list to 32 problem instances and obtain high-quality solutions, very quickly.

Recently, several general optimization algorithms based on the demon algorithm from statistical physics have been developed and tested on a few traveling salesman problems with encouraging results. In this paper, we conduct an extensive computational study of 11 annealing-based heuristics for the traveling salesman problem. We code versions of simulated annealing, threshold accepting, record-to-record travel and eight heuristics based on the demon algorithm. We apply each heuristic to 29 traveling salesman problems taken from a well-known online library, compare the results with respect to accuracy and running time and provide insights and suggestions for future work.

In this paper, we propose a procedure, based on statistical design of experiments and gradient descent, that finds effective settings for parameters found in heuristics. We develop our procedure using four experiments. We use our procedure and a small subset of problems to find parameter settings for two new vehicle routing heuristics. We then set the parameters of each heuristic and solve 19 capacity-constrained and 15 capacity-constrained and route-length-constrained vehicle routing problems ranging in size from 50 to 483 customers. We conclude that our procedure is an effective method that deserves serious consideration by both researchers and operations research practitioners.

Over the last five years or so, data smoothing has been used to improve the performance of heuristics that solve combinatorial optimization problems. Data smoothing allows a local search heuristic to escape from a poor, local optimum. In practice, data smoothing has worked well when applied to the traveling salesman problem. In this paper, we conduct an extensive computational study to test the performance of eight smoothing heuristics for the traveling salesman problem. In particular, we apply eight smoothing heuristics and standard versions of two-opt and three-opt to 40 randomly generated Euclidean problems and 30 problems taken from a well-known library of test problems. We compare the solutions generated by the heuristics and provide insight into the behavior of the smoothing heuristics.

In the site-dependent vehicle routing problem, a fleet of heterogeneous vehicles services a set of customers. Typically, there are several vehicle types (for example, small-, medium-, and large-cap...

In the orienteering problem, start and end points are specified along with other locations which have associated scores. Given a fixed amount of time, the goal is to determine a path from the start point to the end point through a subset of locations in order to maximize the total path score. In this paper, a fast and extremely effective heuristic is presented and tested on 67 problems taken from the literature and 40 new test problems. The computational results are presented in detail.

In the team orienteering problem, start and end points are specified along with other locations which have associated scores. Given a fixed amount of time for each of the M members of the team, the goal is to determine M paths from the start point to the end point through a subset of locations in order to maximize the total score. In this paper, a fast and effective heuristic is presented and tested on 353 problems ranging in size from 21 to 102 points. The computational results are presented in detail.

Over the last 35 years or so, researchers have proposed a variety of ways to estimate the length of an optimal traveling salesman tour. Some of the estimators are asymptotic in nature, while others are equations that relate tour length to various independent variables such as the number of points in a problem, size of a problem's service area, and density of points. In this paper, we develop simple, empirically based estimators of the optimal tour length using regression and neural network models and show that these models can produce reasonably good estimates easily.

In this paper, a new heuristic for the period traveling salesman problem is presented. Our heuristic is fast and simple and has improved upon previous best-known solutions. In addition, we have generated a variety of challenging, new test problems. Our new heuristic is shown to perform well on these new problems.

In the Close-Enough Traveling Salesman Problem (CETSP), if a salesman is within a specified distance of a node, then the node has been visited. This paper presents a method for solving the CETSP that is based on Steiner zones. We generate test problems and conduct extensive computational experiments comparing our method to other heuristics. Overall, our method is very fast and improves upon heuristics from the literature.

SYNOPTIC ABSTRACTIn this paper, the multi-depot vehicle routing problem is reviewed and a new heuristic is presented. The heuristic is fast and simple and improves upon previous best-known solutions. In addition, we generate a variety of new test problems. The new heuristic is shown to perform well on these problems.

Weight annealing is a metaheuristic that has been recently proposed in the physics literature. We develop a weight annealing-based algorithm for solving four variants of the two-dimensional bin packing problem. We apply our algorithm to 500 benchmark instances and find that it quickly produces very high-quality solutions that are comparable to the best published results.

In this chapter, we use genetic algorithms (GAs) to solve the generalized orienteering problem (GOP). In the orienteering problem (OP), we are given a transportation network in which a start point and an end point are specified, and other points have associated scores. Given a fixed amount of time, the goal is to determine a path from start to end through a subset of the other locations in order to maximize the total path score. In the GOP, each point has a score with respect to a number of attributes (e.g., natural beauty, historical significance, cultural and educational attractions, and business opportunities) and the overall objective function is nonlinear. The GOP is more difficult than the OP, which is itself NP-hard. An effective heuristic using artificial neural networks (ANNs), however, has been designed to solve the GOP. In this chapter, we show that a straightforward GA can yield comparable results.

In the standard version of the traveling salesman problem (TSP), we are given a set of customers located in and around a city and the distances between each pair of customers, and need to find the shortest tour that visits each customer exactly once. Suppose that some of the customers are located in the center of the city. Within a window of time, center city becomes congested so that the time to travel between customers takes longer. Clearly, we would like to construct a tour that avoids visiting customers when the center of the city is congested. This variant of the TSP is known as the time dependent TSP (TDTSP). We review the literature on the TDTSP, develop two solution algorithms, and report computational experience with our algorithms.

In the standard, capacitated vehicle routing problem (VRP), a homogeneous fleet of vehicles services a set of customers from a single depot. Each vehicle has a fixed capacity that cannot be exceeded and each customer has a known demand that must be satisfied. Each customer must be serviced by exactly one visit of a single vehicle and each vehicle must leave and return to the depot. There may be route-length restrictions that limit the distance traveled by each vehicle. The objective is to generate a sequence of deliveries for each vehicle so that all customers are serviced and the total distance traveled by the fleet is minimized.