关键词: 车辆路径问题, 整车取送货, 订单选择, 时间窗分割近似算法, 列生成

Abstract: Due to the convenience of the “door-to-door” service provided by trucks, full truckload transportation services, such as container truck transportation, have become quite common. Faced with fluctuating demand, transportation companies typically maintain a small fleet of their own vehicles on a regular basis and outsource some orders during peak demand periods to reduce costs. However, outsourcing can lead to a loss of control over transportation organization and service quality. Consequently, when deciding to outsource orders, transportation companies often consider certain very important orders that should not be outsourced. The decision-making problem for full truckload transportation restricting some orders to be outsourced requires solving a full truckload pickup and delivery routing problem with order selection restriction (FTPDRP-OSR), which is complex. Existing models and algorithms find it challenging to directly address this problem.
To overcome the above research gap, this paper establishes an arc-based mixed integer linear programming model and a set-partitioning binary programming model for the FTPDRP-OSR, respectively. The properties of the binary programming model are analyzed, reducing the number of decision variables. Since the problem at hand is an extension of the multiple travelling salesman problem, which is a NP hard problem, by directly using a mixed integer programming solver, it will be difficult to obtain satisfactory solutions within a given time period when the order scale is large. Therefore, a column-generation-based labeling dynamic programming algorithm and a branch-and-price algorithm are designed. In both algorithms, solutions generated by a time-window partitioning approximation algorithm serve as initial solutions; labels and dominance rules are customized for the order selection restriction; the branching strategy in the branch-and-price algorithm adopts the most infeasible branching strategy, prioritizing variables with fractional parts closest to 0.5 for branching.
To verify the effectiveness of the proposed model and algorithms, numerical experiments are designed for randomly generated instances. The results of the numerical experiments indicate that the branch-and-price algorithm can obtain exact solutions for small-scale instances, albeit taking more time than directly solving with a mixed integer programming solver (CPLEX). However, in large-scale instances, the column-generation-based label dynamic programming algorithm performs better than directly solving with CPLEX. Within an hour ofsolving time for large-scale instances, the gap between the upper and lower bounds for the former is 0.02%, compared to 6.48% for the latter, and the average optimal solution obtained by the former reduces by 1.46% compared to the best solution obtained by the latter.
This paper addresses the single-depot scenario of the FTPDRP-OSR. In reality, many transportation companies operate with multiple depots. Considering the FTPDRP-OSR with multiple depots more closely reflects real-world scenarios and has greater practical significance. However, when considering the multi-depot FTPDRP-OSR, the problem scale and the dimension of decision variables increase significantly, making the solution more challenging. In the future, the proposed algorithms will be extended to the multi-depot scenario of FTPDRP-OSR. By employing a decomposition strategy, the multi-depot scenario can be transformed into multiple single-depot scenarios for solving. Moreover, in practice, transportation and service times of trucks often exhibit randomness, while this paper only considers deterministic cases. Exploring the FTPDRP-OSR with stochastic times presents another research direction.

Key words: vehicle routing problem, truckload pickup and delivery, order selection, time-window-partition based-approximation algorithm, column generation