An Exact Approach for Solving Pickup-and-Delivery Traveling Salesman Problems with Neighborhoods

This paper studies a variant of the traveling salesman problem called the pickup-and-delivery traveling salesman problem with neighborhoods that combines traditional pickup and delivery requirements with the flexibility of visiting the customers at locations within compact neighborhoods of arbitrary shape. We derive two optimality conditions for the problem, a local condition that verifies whether a … Read more

An Exact Solution Method for the TSP with Drone Based on Decomposition

The Traveling Salesperson Problem with Drone (TSP–D) is a routing model in which a given set of customer locations must be visited in the least amount of time, either by a truck route starting and ending at a depot or by a drone dispatched from the truck en route. We study the TSP–D model and … Read more

Exact and Heuristic Algorithms for the Carrier-Vehicle Traveling Salesman Problem

This paper presents new structural properties for the Carrier-Vehicle Traveling Salesman Problem. The authors provide a new mixed integer second order conic optimization formulation, with associated optimality cuts based on the structural properties, and an Iterated Local Search (ILS) algorithm. Computational experiments on instances from the literature demonstrate the superiority of the new formulation to … Read more

Dynamic programming for the time-dependent traveling salesman problem with time windows

The recent growth of direct-to-consumer deliveries has stressed the importance of last-mile logistics, becoming one of the critical factors in city planning. One of the key factors lies in the last-mile deliveries, reaching in some cases nearly 50% of the overall parcel delivery cost. Different variants of the the well-known Traveling Salesman Problem (TSP) arise … Read more

Exact Methods for the Traveling Salesman Problem with Drone

Efficiently handling last-mile deliveries becomes more and more important nowadays. Using drones to support classical vehicles allows improving delivery schedules as long as efficient solution methods to plan last-mile deliveries with drones are available. We study exact solution approaches for some variants of the traveling salesman problem with drone (TSP-D) in which a truck and … Read more

Solving Time Dependent Traveling Salesman Problems with Time Windows

We present a new solution approach for the Time Dependent Traveling Salesman Prob- lem with Time Windows. This problem considers a salesman who departs from his home, has to visit a number of cities within a pre-determined period of time, and then returns home. The problem allows for travel times that can depend on the … Read more

Exact Methods for Solving Traveling Salesman Problems with Pickup and Delivery in Real Time

The Traveling Salesman Problem with Pickup and Delivery (TSPPD) describes the problem of finding a minimum cost path in which pickups precede their associated deliveries. The TSPPD is particularly important in the growing field of Dynamic Pickup and Delivery Problems (DPDP). These include the many-to-many Dial-A-Ride Problems (DARP) of companies such as Uber and Lyft, … Read more

The Traveling Salesperson Problem with Forbidden Neighborhoods on Regular 3D Grids

We study the traveling salesperson problem with forbidden neighborhoods (TSPFN) on regular three-dimensional grids. The TSPFN asks for a shortest tour over all grid points such that successive points along a tour have at least some given distance. We present optimal solutions and explicit construction schemes for the Euclidean TSP and the TSPFN where edges … Read more

Closed Almost Knight’s Tours on 2D and 3D Chessboards

Let a (generalized) chessboard in two or three dimensions be given. A closed knight’s tour is defined as a Hamiltonian cycle over all cells of the chessboard where all moves are knight’s moves, i.,e. have length 5^0.5. It is well-characterized for which chessboard sizes it is not possible to construct a closed knight’s tour. On … Read more

The Traveling Salesman Problem on Grids with Forbidden Neighborhoods

We introduce the Traveling Salesman Problem with forbidden neighborhoods (TSPFN). This is an extension of the Euclidean TSP in the plane where direct connections between points that are too close are forbidden. The TSPFN is motivated by an application in laser beam melting. In the production of a workpiece in several layers using this method … Read more