Article Preview
Top1. Introduction
Vehicle Routing Problem (VRP) is a key component of distribution and logistics management. It consists in finding an optimal set of trips for a fleet of vehicles which must serve a predefined set of customers. The most studied variant in transportation logistics is capacitated VRP (CVRP) (Sbai et al. (2020)).
The CVRP can be extended to the VRP with time windows (VRPTW) by adding time windows in which deliveries need to take place. Another variant is the VRP with pickups and deliveries (VRPPD) in which orders may be picked up and delivered. More recently, a VRP with backhauls (VRPB) or the linehaul-backhaul problem has been studied, when VRP involving both delivery (linehaul) and pickup (backhaul) points. In contrast to the classical VRP, a practical important variant of this problem is the dynamic VRP (DVRP) where new customer demands change during operation reference.
In real life, companies are faced with a large number of additional constraints which increase the com- plexity of the problem. For example, the capacitated vehicle routing problem with two-dimensional loading constraints (2L-CVRP) includes the routing and loading aspects simultaneously.
The 2L-CVRP is defined as giving a central depot of a homogenous fleet of vehicles driving between two customers, or from the depot to a customer, to deliver requested product. Products to be de- livered are thought to be rectangular shaped items. The objective of the 2L-CVRP is to find the routes of the vehicles of the fleet, minimizing the delivery costs, and determining, for a given route, the feasible two-dimensional orthogonal loading arrangement of the transported items into the vehicle loading surface.
Planning the distribution and pick-up of goods as a VRP with Backhauls (VRPB) in an efficient manner is an appropriate way to reduce logistic cost and improve the quality of service. Therefore, we consider the 2L-CVRP with backhaul, in which a set of customers can be divided in two distinct sets: the set of linehaul (deliver) and the set of backhaul (pickup) customers. For each route two packing plans have to be provided that stow all boxes of all visited linehaul and backhaul customers, respectively, taking into account the additional packing constraints.
All the existing research has been studied the 2L-VRPB as a static case in which all information and problem parameters are assumed to be known in advance, and the related decisions are made prior to the start of plan execution. However, in real-life applications, a new arrived order such as a courier, money-transfer and repair-maintenance services can be happen over time and thus trouble the optimal routing schedule that was originally invented.
Therefore, we address a Dynamic Vehicle Routing Problem with Backhaul and 2-dimensional loading constraints (2L-DVRPB) in which new customer orders with two-dimension and order cancellations continually happen over time of backhaul.
This problem is a combination of two most important NP-hard optimization problems in distribution logistics, the Dynamic Vehicle Routing Problem with Backhaul constraint (DVRPB) and the Two-dimensional Bin Packing Problem (2BPP).
To solve the 2L-DVRPB, we propose an Adaptive Genetic Algorithm (AGA) and a new packing heuristic named Min lost area heuristic (MILAH).
Moreover, the 2L-DVRPB has many industrial applications in different fields of real life, such as shipping and transportation industry. So, we applied our approach in a real case study of the dis- tribution of two dimension parcels in Regional Post Office of the region of Jendouba in the North of Tunisia.
The remainder of this paper is structured as follows. The related literature review is provided in Sec- tion 2. Section 3 and 4 present a brief description and a Mathematical formulation of the 2L-DVRPB problem. Section 5 describes the proposed Genetic Algorithm for solving the 2L-DVRPB. In Section 6, a set of heuristics for the loading subproblem are given. In section 7 and 8, the efficiency of the proposed approach is investigated with experimental results and a real case study. In Section 7, we end with some concluding remarks and future works.