Suchergebnisse

Abstract: This paper deals with a special vehicle routing problem with backhauls where each customer receives items from a depot and, at the same time, returns items back to the depot. Moreover, time windows are assumed and three-dimensional loading constraints are to be observed, i.e. the items are three-dimensional boxes and packing constraints, e.g. regarding load stability, are to be met. The resulting problem is the vehicle routing problem with simultaneous delivery and pickup (VRPSDP), time windows, and three-dimensional loading constraints (3L-VRPSDPTW). This problem occurs, for example, if retail stores are supplied by a central warehouse and wish to return packaging material. A particular challenge of the problem is to transport delivery and pickup items simultaneously on the same vehicle. In order to avoid any reloading effort during a tour, we consider two different loading approaches of vehicles: (i) loading from the back side with separation of the loading space into a delivery section and a pickup section and (ii) loading at the long side. A hybrid algorithm is proposed for the 3L-VRPSDPTW consisting of an adaptive large neighbourhood search for the routing and different packing heuristics for the loading part of the problem. Extensive numerical experiments are conducted with VRPSDP instances from the literature and newly generated instances for the 3L- VRPSDPTW.

Supermarkets typically order their goods from a centrally located distribution center (warehouse). Each order that the warehouse receives is characterized by the requested items, the location of the respective supermarket and a due date by which the items have to be delivered. For processing an order, a human operator (order picker) retrieves the requested items from their storage locations in the warehouse first. The items are then available for shipment and loaded on the vehicle which performs the tour including the respective location of the supermarket. Whether and to which extent a due date is violated (tardiness) depends on the composition of the tours, the corresponding routes and the start dates of the tours (vehicle routing subproblem). The start date of a tour, however, is also affected by the assignment of orders to pickers and the sequence according to which the orders are processed by the pickers (order picking subproblem). Although both subproblems are closely interconnected, they have not been considered simultaneously in the literature so far. In this paper, an iterated local search algorithm is designed for the simultaneous solution of the subproblems. By means of extensive numerical experiments, it is shown that the proposed approach is able to generate high-quality solutions even for large instances. Furthermore, the economic benefits of an integrated solution are investigated. Problem classes are identified, where the sequential solution of the subproblems leads to acceptable results, and it is pointed out in which cases an integrated solution is inevitable.

Multi-compartment vehicle routing problems arise in a variety of problem settings in which different product types have to be transported separated from each other. In this paper, a problem variant which occurs in the context of glass waste recycling is considered. In this problem, a set of locations exists, each of which offering a number of containers for the collection of different types of glass waste (e.g. colorless, green, brown glass). In order to pick up the contents from the containers, a fleet of homogeneous disposal vehicles is available. Individually for each disposal vehicle, the capacity can be discretely separated into a limited number of compartments to which different glass waste types are assigned. The objective of the problem is to minimize the total distance to be travelled by the disposal vehicles. For solving this problem to optimality, a branch-and-cut algorithm has been developed and implemented. Extensive numerical experiments have been conducted in order to evaluate the algorithm and to gain insights into the problem structure. The corresponding results show that the algorithm is able to solve instances with up to 50 locations to optimality and that it reduces the computing time by 87% compared to instances from the literature. Additional experiments give managerial insights into the use of different variants of compartments with flexible sizes.