Refine
Document Type
- Working paper (2)
- Doctoral thesis (1)
Has Fulltext
- yes (3)
Is part of the Bibliography
- no (3)
Language
- English (3)
Keywords
- Graph refinement (3) (remove)
Institute
One of the standard approaches for solving discrete optimization problems which include the aspect of time, such as the traveling salesman problem with time windows, is to derive a so-called time-indexed formulation. If the problem has an underlying structure that can be described by a graph, the time-indexed formulation is usually based on a different, extended graph, commonly referred to as the time-expanded graph. The time-expanded graph can often be derived in such a way that all time constraints are incorporated in its topology, and therefore algorithms for the corresponding time-independent variant become applicable. The downside of this approach is that the sets of vertices and arcs of the time-expanded graph are much larger than the ones of the original graph. In recent works, however, it has been shown that for many practical applications a partial graph expansion that might contain time-infeasible paths, often suffices to find a proven optimal solution. These approaches, instead, iteratively refine the original graph and solve a relaxation of the time-expanded formulation in each iteration. When the solution of the current relaxation allows for a feasible schedule, an optimal solution can be derived from it and the algorithm terminates.
In this work, we first present new ideas that allow for the propagation of information about the optimal solution of a coarser graph to a more refined graph and show how these can be used in algorithms. More precisely, we present two general algorithms for solving Mixed Integer Linear Program formulations which we call iterative refinement and branch-and-refine. Iterative refinement basically is solving relaxations of the problem until a feasible solution to the original problem is found. Branch-and-refine is a kind of branch-and-bound algorithm that allows for the graph refinement to be carried out during the exploration of the branch-and-bound tree. For demonstrating the practical relevance of these algorithms, we not only study them in the context of academic examples but also apply them to two real-world problems. The first is a problem from the literature, where small passenger air-crafts have to be routed and scheduled to serve flight requests while fulfilling a variety of conditions on, for example, fuel consumption, weight, and detours. We show here that refinement algorithms can be used to improve the best known results from the literature. The second problem we consider is the task of optimally scheduling deliveries and charging times of delivery robots such that delays are minimized. In this case, we show that refinement algorithms perform better than a direct solution approach making use of state-of-the-art solvers.
In recent years parcel volumes reached record highs. The logistics industry is seeking new innovative concepts to keep pace. For densely populated areas delivery robots are a promising alternative to conventional trucking. These electric robots drive autonomously on sidewalks and deliver urgent goods, such as express parcels, medicine, or meals. The limited cargo space and battery capacity of these vehicles necessitates a depot visit after each customer served. The problem can be formulated as an electric vehicle routing problem with soft time windows and a single unit capacity. The goal is to serve all customers such that the quadratic sum of delays is minimized and each vehicle operates within its battery bounds. To solve this problem, we formulate an MIQP and present an expanded formulation based on a layered graph. For this layered graph we derive two solution approaches based on relaxations, which use less nodes and arcs. The first, Iterative Refinement, always solves the current relaxation to optimality and refines the graph if the solution is not feasible for the expanded formulation. This is repeated until a proven optimal solution is found. The second, Branch and Refine, integrates the graph refinement into a branch and bound framework avoiding restarts. Computational experiments performed on modified Solomon instances demonstrate the advantage of using our solution approaches and show that Branch and Refine outperforms Iterative Refinement in all studied parameter configurations.
One of the standard approaches for solving time-dependent discrete optimization problems, such as the travelling salesman problem with time-windows or the shortest path problem with time-windows is to derive a so-called time-indexed formulation. If the problem has an underlying structure that can be described by a graph, the time-indexed formulation is usually based on a different, extended graph, commonly referred to as the time-expanded graph. The time-expanded graph can often be derived in such a way that all time constraints are incorporated in its topology, and therefore algorithms for the corresponding time-independent variant become applicable. The downside of this approach is, that the sets of vertices and arcs of the time-expanded graph are much larger than the ones of the original graph. In recent works, however, it has been shown that for many practical applications a partial graph expansion, that might contain time infeasible paths, often suffices to find a proven optimal solution. These approaches, instead, iteratively refine the original graph and solve a relaxation of the time-expanded formulation in each iteration. When the solution of the current relaxation is time feasible an optimal solution can be derived from it and the algorithm terminates. In this work we present new ideas, that allow for the propagation of information about the optimal solution of a coarser graph to a more refined graph and show how these can be used in algorithms, which are based on graph refinement. More precisely we present a new algorithm for solving Mixed Integer Linear Program (MILP) formulations of time-dependent problems that allows for the graph refinement to be carried out during the exploration of the branch-and-bound tree instead of restarting whenever the optimal solution was found to be infeasible. For demonstrating the practical relevance of this algorithm we present numerical results on its application to the shortest path problem with time-windows and the traveling salesman problem with time-windows.