张烜荧,胡 蓉,钱 斌

(昆明理工大学信息工程与自动化学院自动化系,云南昆明 650500;昆明理工大学云南省人工智能重点实验室,云南昆明 650500)

1 引言

随着“制造强国战略”的实施,在推动先进制造业迅速发展的同时,现代物流业的高质量发展也成为大势所趋.在物流系统中,配送是核心部分,而车辆路径问题(vehicle routing problem,VRP)是其中的重要一环.传统的VRP主要描述为组织一个车队,安排适当的行车路线为一定数量的客户提供送货服务,并能在满足车载量、行车里程等约束条件下,达到诸如车辆行驶总里程最短,成本最小,耗时最少等目的.随着资源需求的增加与供给双向流通方式的快速发展,以及物流企业对降低成本、保护环境的注重,考虑逆向物流的车辆路径问题开始受到重视.此外,日益激烈的市场竞争逼迫企业在满足客户需求的同时要考虑提高客户满意度.在此背景下,研究带软时间窗的同时取送货车辆路径问题(vehicle routing problem with simultaneous pickup and delivery and soft time windows,VRPSPDSTW)具有重要意义.由于带时间窗的同时取送货车辆路径问题(vehicle routing problem with simultaneous pickup and delivery and time windows,VRPSPDTW)为NP-hard问题[1],而VRPSPDTW可归约为VRPSPDSTW,故VRPSPDSTW也属于NPhard问题,对其展开研究具有较大理论价值.

VRPSPDSTW的求解算法主要分为两类.一类是运筹学算法,包括分支定价、动态规划和拉格朗日松弛等[2–8],基本都是用于求解单目标问题.此类算法以线性代数和几何分析为基本工具,利用问题优化目标函数和约束式的结构信息构造搜索,可在几分钟至几十分钟内获取较小规模问题(客户数小于等于20)的最优解.但……