周 迅,张惠珍
(上海理工大学管理学院,上海 200093)
设施选址与车辆路径是供应链网络中的两个关键问题,对公司运营和盈利有着重大影响。因此,设施选址问题[1](Facility Location Problem,FLP)与车辆路径问题[2](Vehicle Routing Problem,VRP)引起了众多研究者关注。随着物流系统的日益复杂,选址和运输之间的耦合越来越高,储运之间关系日益密切。在解决许多实际问题时,应综合考虑两者关系进行决策,从而实现整体优化,由此形成具有容量的设施选址问题(Capacitated Location Routing Problem,CLRP)[3],该问题是当前物流研究热点。近年来,越来越多的企业将主要精力投入到核心业务中以获得竞争优势,同时将企业物流活动外包给第三方物流供应商。通常服务车辆由第三方物流公司拥有,在完成客户服务之后,这些车辆返回到第三方物流公司,而不是企业配送中心或仓库,因此带来由第三方物流配送的开放式选址路径问题(Open Capacitated Location Routing Problem,OCLRP)[4]。CLRP 与相应OCLRP 区别如图1 所示。图中实线部分给出了OCLRP 问题解决方案,每辆车在为最后一个客户结束服务后无需回到仓库;图中实线和虚线整体构成了相应CL⁃RP 解决问题的方案,车辆在为最后一个客户结束服务后需返回仓库。从图1 可以看出,CLRP 与OCLRP 的主要区别为OCLRP 中的每条路径都是哈密顿路径,而CLRP 中的每条路径都是哈密顿回路。

Fig.1 The difference between CLRP and corresponding OCLRP图1 CLRP 与相应OCLRP 之间的区别
在实际配送中,OCLRP 会面临各种限制条件。比如,很多客户对交货期都有一定要求。配送服务最好提前在约定的时间窗口内完成,否则会因违反时间窗口约束而受到处罚。……