Multi-criteria parcel locker-based vehicle routing with pickup and delivery

In this paper a variant of Vehicle Routing Problem with Pickup and Delivery for parcel locker-based delivery is considered. The mathematical model of the problem is formulated with a bi-criteria goal function to minimize both the total distance traveled by all vehicles and the maximal order delivery time. The model assumes alternative delivery locations, where the order has to be delivered to the closest locations where its originally indented location has no available lockers left. The problem considers two types of orders (delivery and pickup) and accounts for vehicle and locker capacities, a possibility of non-symmetric distances, varying in-day travel times and order size categories. An order-based solution representation is proposed. A procedure to compute the goal function value and establish solution feasibility via the use of Discrete Event Simulation is presented. Three additional solution representations are proposed based on the idea of grouping orders and a number of properties showcasing their advantages and drawbacks are established. A procedure to generate problem instances based on real-life data is proposed and used to construct a basic benchmark dataset with 320 problem instances with number of orders ranging from 70 to 7177. Two heuristic solving methods are proposed: a greedy algorithm and a Genetic Algorithm metaheuristic. Each algorithm was implemented in four variants, one for each of the proposed solution representations. A number of computer experiments are performed on the proposed benchmark dataset and its derivatives, to establish the effectiveness of solution representations and algorithms, as well as to research the influence of several parameters on the obtained solutions and their feasibility. Results indicate that the alternative representations vastly outperform the standard representation in terms of Hyper-volume Indicator and both considered criteria. The genetic Algorithm also significantly outperforms the greedy method, although the advantage decreases with the increase of the number of orders. Other experiments indicate how vehicle-to-order, delivery-to-pickup, and locker occupancy ratios affect the feasibility of the solution.