We consider multi-agent transport task problems where, e.g. in a factory setting, items have to be delivered from a given start to a goal pose while the delivering robots need to avoid collisions with each other on the floor. We introduce a Task Conflict-Based Search (TCBS) Algorithm to solve the combined delivery task allocation and multi-agent path planning problem optimally. The problem is known to be NP-hard and the optimal solver cannot scale. However, we introduce it as a baseline to evaluate the sub-optimality of other approaches. We show experimental results that compare our solver with different sub-optimal ones in terms of regret.
In the pickup and delivery problem with time windows (PDPTW), vehicles have to transport loads from origins to destinations respecting capacity and time constraints. In this paper, we present a two-phase method to solve the PDPTW. In the first phase, we apply a novel construction heuristics to generate an initial solution. In the second phase, a tabu search method is proposed to improve the solution. Another contribution of this paper is a strategy to generate good problem instances and benchmarking solutions for PDPTW, based on Solomon's benchmark test cases for VRPTW. Experimental results show that our approach yields very good solutions when compared with the benchmarking solutions. The concept of public logistics terminals (multi-company distribution centers) has been proposed in Japan to help alleviate traffic congestion, environment, energy and labor costs. These facilities allow more efficient logistics systems to be established and they facilitate the implementation of advanced information systems and cooperative freight systems. This paper describes a mathematical model developed for determining the optimal size and location of public logistics terminals. Queuing theory and nonlinear programming techniques are used to determine the best solution. The model explicitly takes into account traffic conditions in the network and was successfully applied to an actual road network in the Kyoto-Osaka area in Japan. This paper is the second part of a comprehensive survey on routing problems involving pickups and deliveries. Basically, two problem classes can be distinguished. The first part dealt with the transportation of goods from the depot to linehaul customers and from backhaul customers to the depot. The second part now considers all those problems where goods are transported between pickup and delivery locations, denoted as Vehicle Routing Problems with Pickups and Deliveries (VRPPD). These are the Pickup and Delivery Vehicle Routing Problem (PDVRP – unpaired pickup and delivery points), the classical Pickup and Delivery Problem (PDP – paired pickup and delivery points), and the Dial-A-Ride Problem (DARP – passenger transportation between paired pickup and delivery points and user inconvenience taken into consideration). Single as well as multi vehicle mathematical problem formulations for all three VRPPD types are given, and the respective exact, heuristic, and metaheuristic solution methods are discussed. In pickup and delivery problems vehicles have to transport loads from origins to destinations without transshipment at intermediate locations. In this paper, we discuss several characteristics that distinguish them from standard vehicle routing problems and present a survey of the problem types and solution methods found in the literature. In this paper, we introduce the Intersection Graph Method for solving the AGV Flow Path Optimization Model developed by Kaspi and Tanchoco (1990). A branch-and-bound procedure is described wherein only a reduced subset of all nodes in the flow path network is considered. Only intersection nodes are used to obtain optimal solutions. Two examples are given to illustrate the proposed method.