A Branch-and-Price Algorithm for Optimal Routing of Delivery Robots

Simple item page
dc.contributor.authorSchaudt, Stefan
dc.contributor.authorClausen, Uwe
dc.contributor.authorKlein, Nicklas
dc.date.accessioned2022-04-29T17:28:31Z
dc.date.available2022-04-29T17:28:31Z
dc.date.issued2022-05-01
dc.description.abstractIncreasing parcel volumes, environmental challenges, and customer expectations have made innovative delivery concepts for last-mile logistics essential in recent years. Autonomous delivery vehicles such as delivery robots or drones are tested worldwide. In this work, we examine the use of electrical delivery robots to optimize a last-mile network. The network consists of a fleet of homogeneous single-unit capacity robots, depots equipped with recharging stations, and customers. Each customers is defined by a time window and a profit. The goal is to find a set of tours that maximizes the total collected profit. These tours have to respect the customers' time windows and battery constraints of the robots. We present a branch-and-price algorithm to solve this combinatorial optimization problem exactly. Within this algorithm, the problem of finding feasible tours arises. To decide on the feasibility of a tour, we present a polynomial dynamic program and prove its correctness. The computational studies on modified benchmark instances show that the algorithm can solve instances that have realistic time window lengths and up to 144 customers in a reasonable time.en
dc.identifier.urihttp://hdl.handle.net/2003/40889
dc.identifier.urihttp://dx.doi.org/10.17877/DE290R-22746
dc.language.isoende
dc.subjectbranch-and-priceen
dc.subjectteam orienteeringen
dc.subjectvehicle routing problemen
dc.subjectmultiple depotsen
dc.subjectpartial rechargingen
dc.subjectelectric vehicle routing problemen
dc.subjectexact algorithmen
dc.subjectdelivery robotsen
dc.subjectdynamic programen
dc.subjectlast-mileen
dc.subject.ddc620
dc.subject.ddc670
dc.subject.rswkBranch-and-Price-Methodede
dc.subject.rswkMehrdepotproblemde
dc.subject.rswkBeladende
dc.subject.rswkAlgorithmusde
dc.subject.rswkServiceroboterde
dc.subject.rswkMobiler Roboterde
dc.subject.rswkLogistikde
dc.subject.rswkCity-Logistikde
dc.titleA Branch-and-Price Algorithm for Optimal Routing of Delivery Robotsen
dc.typeTextde
dc.type.publicationtypepreprintde
dcterms.accessRightsopen access
eldorado.secondarypublicationfalsede

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
A Branch-and-Price Algorithm for Optimal Routing of Delivery Robots - Preprint.pdf
Size:
679.18 KB
Format:
Adobe Portable Document Format
Description:
DNB
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
4.85 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Institut für Transportlogistik