Hybrid algorithms for the vehicle routing problem with pickup and delivery and two-dimensional loading constraints / Dirk Männel
Loading...
Download829.44 KB
Hybrid algorithms for the vehicle routing problem with pickup and delivery and two-dimensional loading constraints
Discovery
895078007
URN
urn:nbn:de:gbv:3:2-75433
DOI
ISBN
ISSN
Koordinaten
Skalierung
Author
dc.contributor.contributor
Other contributor
Publication history
Magdeburg : Otto von Guericke University Magdeburg, Faculty of Economics and Management, [2017]
Content
1 Online-Ressource (37 Seiten = 0,81 MB) : Illustrationen
Edition
Language
eng
Comment
Abstract
We extend the classical Pickup and Delivery Problem (PDP) to an integrated routing and two-dimensional loading problem, called PDP with two-dimensional loading constraints (2L-PDP). A set of routes of minimum total length has to be determined such that each request is transported from a loading site to the corresponding unloading site. Each request consists of a given set of 2D rectangular items with a certain weight. The vehicles have a weight capacity and a rectangular two-dimensional loading area. All loading and unloading operations must be done exclusively by movements parallel to the longitudinal axis of the loading area of a vehicle and without moving items of other requests. Furthermore, each item must not be moved after loading and before unloading. The problem is of interest for the transport of rectangular-shaped items that cannot be stacked one on top of the other because of their weight, fragility or large dimensions. The 2L-PDP also generalizes the well-known Capacitated Vehicle Routing Problem with Two-dimensional Loading Constraints (2L-CVRP), in which the demand of each customer is to be transported from the depot to the customer’s unloading site. This paper proposes two hybrid algorithms for solving the 2L-PDP and each one consists of a routing and a packing procedure. Within both approaches, the routing procedure modifies a well-known large neighborhood search for the one-dimensional PDP and the packing procedure uses six different constructive heuristics for packing the items. Computational experiments were carried out using 60 newly proposed 2L-PDP benchmark instances with up to 150 requests.
Series
Working paper series ; no. 2017, 10 ppn:58927368X