@techreport{GnegelSchaudtClausenetal.2021, type = {Working Paper}, author = {Gnegel, Fabian and Schaudt, Stefan and Clausen, Uwe and F{\"u}genschuh, Armin}, title = {A 2D layered graph approach for scheduling delivery robots}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-5493}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-54931}, year = {2021}, abstract = {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.}, subject = {Delivery robots; Electric vehicle routing problem; Graph refinement; Layered graphs; Partial recharging; Lieferroboter; Streckenplanung f{\"u}r elektrische Fahrzeuge; Graphenverfeinerung; Geschichtete Graphen; Partielles Aufladen; Mobiler Roboter; Tourenplanung; Optimierung}, language = {en} } @article{GnegelSchaudtClausenetal.2024, author = {Gnegel, Fabian and Schaudt, Stefan and Clausen, Uwe and F{\"u}genschuh, Armin}, title = {A graph-refinement algorithm to minimize squared delivery delays using parcel robots}, series = {Mathematics}, volume = {12}, journal = {Mathematics}, publisher = {MDPI}, address = {Basel}, issn = {2227-7390}, doi = {10.3390/math12203201}, year = {2024}, abstract = {In recent years, parcel volumes have reached record highs, prompting the logistics industry to explore innovative solutions to meet growing demand. In densely populated areas, delivery robots offer a promising alternative to traditional truck-based delivery systems. These autonomous electric robots operate on sidewalks and deliver time-sensitive goods, such as express parcels, medicine and meals. However, their limited cargo capacity and battery life require a return to a depot after each delivery. This challenge can be modeled as an electric vehicle-routing problem with soft time windows and single-unit capacity constraints. The objective is to serve all customers while minimizing the quadratic sum of delivery delays and ensuring each vehicle operates within its battery limitations. To address this problem, we propose a mixed-integer quadratic programming model and introduce an enhanced formulation using a layered graph structure. For this layered graph, we present two solution approaches based on relaxations that reduce the number of nodes and arcs compared to the expanded formulation. The first approach, Iterative Refinement, solves the current relaxation to optimality and refines the graph when the solution is infeasible for the expanded formulation. This process continues until a proven optimal solution is obtained. The second approach, Branch and Refine, integrates graph refinement into a branch-and-bound framework, eliminating the need for restarts. Computational experiments on modified Solomon instances demonstrate the effectiveness of our solution approaches, with Branch and Refine consistently outperforming Iterative Refinement across all tested parameter configurations.}, subject = {Integer programming; Layered graph refinement; Delivery robots; Electric vehicle-routing problem; Partial recharging}, language = {en} }