The Vehicle Scheduling Problem of Third-Party Passenger Finished Vehicle Logistics Transportation: Formulation, Algorithms, and Instances

Abstract

In this article, a vehicle scheduling problem of third-party passenger finished vehicle logistics transportation networks is studied. An integer programming model of open heterogeneous fleet pickup and delivery problem with time windows and split load (OHFPDPTWSL) is established to maximize the total profit, and a hybrid parallel heuristic algorithm combining with path buffer clustering operator (PBC), multi-mark split operator (MMS) and four variable neighborhood search operators (PBCMMSVNSHPA) is proposed to solve this problem with high quality in a relatively short time. The PBC operator with three different clustering types can effectively cluster the orders and the transport vehicles before the route planning, and the MMS operator can greatly reduce the complexity and computation of the path planning at the expense of little algorithm precision. Then a set of instances which represents the realistic characters of OHFPDPTWSL modified from benchmark instances is introduced. The experimental results on these instances show that PBCMMSVNSHPA is suitable for real-time requirement or large-scale dataset, and the experimental results on the actual instance of an enterprise show that this algorithm can solve the instance with 200 orders and 500 vehicles within 3 minutes.

Keywords

• Passenger finished vehicle logistics
• open heterogeneous fleet
• pickup and delivery problem with time windows and split load
• path buffer clustering
• multi-mark split