带订单选择限制的整车取送货路径问题的模型与算法研究  

Model and Algorithm Research on Solving a Truckload Pickup and Delivery Routing Problem Considering Order Selection Restriction

作　　者：张辉 黄敏[2,3] 吴影辉[1] 付亚平 王兴伟 ZHANG Hui;HUANG Min;WU Yinghui;FU Yaping;WANG Xingwei(School of Economics and Management,Jiangsu University of Science and Technology,Zhenjiang 212100,China;College of Information Science and Engineering,Shenyang 110819,China;State Key Laboratory of Synthetical Automation for Process Industries,Shenyang 110819,China;School of Business,Qingdao University,Qingdao 266071,China;College of Computer Science and Engineering,Northeastern University,Shenyang 110169,China)

机构地区：[1]江苏科技大学经济管理学院,江苏镇江212100 [2]东北大学信息科学与工程学院,辽宁沈阳110819 [3]流程工业综合自动化国家重点实验室,辽宁沈阳110819 [4]青岛大学商学院,山东青岛266071 [5]东北大学计算机科学与工程学院,辽宁沈阳110169

出　　处：《运筹与管理》2024年第10期103-109,共7页Operations Research and Management Science

基　　金：国家自然科学基金重点国际(地区)联合研究项目(7162010703);兴辽英才计划项目(XLYC1802115);流程工业综合自动化国家重点实验室基础研究基金项目(2013ZCC11);111海外专家引进孵化计划项目(BC2018010);“高水平海外专家”引进计划项目(G20190006026)。

摘　　要：带订单选择限制的整车取送货路径问题是卡车运输外包决策中一类重要问题。由于订单外包限制约束,使得求解整车取送货路径问题的高精度解比较困难。为解决该问题,本文分别建立了带订单选择限制的整车取送货路径问题的基于弧的混合整数规划模型和集划分模型,设计了基于列生成的标签算法和分支定价精确求解算法。在两种算法中,采用时间窗划分近似算法获得较好的初始解;针对订单选择限制约束定制了标签和支配规则;分支定价算法采用最不可行分支策略,即优先选择小数部分最接近0.5的变量进行分支。数值实验表明,分支定价算法能够求得小规模算例的最优解,但是所用时间大于混合整数规划求解器(CPLEX)直接求解。相比求解器直接求解,基于列生成的标签算法在求解较大规模算例时表现更优,能求得近似最优解;在一小时的求解时间限制下,前者能够求得的上下界的差距为0.02%,后者的上下界的差距为6.48%。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 prop

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

分 类 号：F272[经济管理—企业管理]