Abstract: Due to demand diversity, multi-compartment vehicles are often used to transport goods unfit for mixed loading. Splitting orders according to the type of goods and prioritizing the goods in urgent need can improve the efficiency of logistics service. For goods packed in boxes of regular shape, effective packing scheme can improve the space utilization ratio. Therefore, this paper studies the Threedimensional Loading Multi-compartment Vehicle Routing Problem with Discrete Split Deliveries (3L-MCVRPDSD) and formulates a mixed integer programming model. A Memetic Algorithm (MA) is proposed to solve the model, which designs an order splitting and assembling strategy to track the suborder-vehicle assignment considering discrete split deliveries, as well as the mapping relationship between suborder ordering and vehicle routing. A construction heuristic three-dimensional bin packing strategy is adopted to identify feasible three-dimensional packing schemes. Compared with the result of Genetic Algorithm (GA) and CPLEX, the proposed algorithm is proved to be able to get satisfactory feasible solution in a reasonable time.

Key words: vehicle routing, three-dimensional bin packing problem, multi-compartment, discrete split deliveries, memetic algorithm