考虑路径优化的共同配送站点选址研究

豆训博+李莉

[摘 要]为了降低物流配送距离，提高城市物流的配送效率，文章提出以配送路线最小化为目标，分别建立考虑配送车辆容量和时间窗约束下的两种物流配送路径优化模型。并采用Lingo软件快速求解线性规划问题的优势，引用实例分析，最终求得不同模型下的配送選址最优解。

[关键词]路径优化；配送站点；选址

[DOI]10.13939/j.cnki.zgsc.2017.15.216

配送站点的选址问题（Common distribution site location）是指需求点委托相应的供应商统一在某个地区建立配送站点，集中来自不同供应商的货物，然后向自己所辐射的范围内进行集中配送。

考虑路径优化的配送站点选址是指多辆配送车辆从共同配送站点出发，按照一定的路径配送给各个需求点，每个需求点只能被访问一次。目前在Lingo语言求解选址方面，Massimo Paolucci（2011）在Vehicle Routing Problem 中建立了相应的配送路径时间窗求解模型（VRPTW）；王林等（2008）在一般要求下建立混合整数规划选址模型来确定配送站点选址最佳方案；丁晓东等（2009）建立0～1混合整数规划模型求解选址问题；徐丽蕊（2013）在求解路径优化模型中讨论了考虑容量约束配送路径优化问题。本文主要讨论：一是考虑车辆载重量约束；二是进行载重量和时间窗双重约束条件，建立数学模型，然后基于Lingo软件进行配送站点的选址进行求解，得出最优的路径长度。

1 问题描述与数学模型

考虑路径优化的选址问题可描述为：从配送站点出发的车辆对辖区范围内的需求点进行产品配送，结合相应约束要求（比如，车辆容量或者是时间窗约束条件）进行配送，配送结束后，车辆最终返回配送站点。然而，运输路径的长短在运费和配送效率方面至关重要。

1.1 共同配送站点CVRP问题选址模型

CVRP问题选址可描述为：从配送站点出发的车辆，结合车辆载重量约束，对辐射范围内的需求点进行产品配送，配送结束后，车辆最终返回配送站点的过程。

为了便于建立选址模型，相应的假设满足以下条件：①满足每个需求点的配送要求，且由一辆配送车辆进行送货作业；②车辆在完成所有需求点服务后，最后返回配送站点；③配送车辆的最大载重量应大于等于该配送路径上各需求点的需求量之和。

1.2 共同配送站点CVRPTW问题选址模型

CVRPTW问题选址可描述为：从配送站点出发的车辆，结合车辆载重量和配送时间窗等双重约束，对辐射范围内的需求点进行产品配送，车辆在完成所有需求点服务后，最终返回配送站点的过程。

同样，为了便于建立选址模型，相应的假设应满足以下条件：①满足每个需求点的配送要求，且由一辆配送车辆进行送货作业；②车辆在完成所有需求点服务后，最后返回配送站点；③配送车辆的最大载重量应大于等于该配送路径上各需求点的需求量之和；④各个需求点配送活动应在限制的时间窗范围内完成。

2 应用实例与结果分析

本文以乌鲁木齐市社区蔬菜配送直销点作为需求点进行分析，假设社区有16个社区配送直销点，需要建立一个配送站点，根据实地考察和专家意见，从中选出了3个地点，分别为直销点2、直销点9和直销点15作为备选配送站点，结合本文两种模型选出最优的一个备选配送站点作为其他社区直销点的配送站点，该配送站点将拥有2吨的货车10辆进行配送作业活动，运行速度30km/h，允许的最大运行时间为2h，允许的最大运行距离为30km，其中ai表示为直销点i的允许最早时间，bi表示直销点i的最晚时间，[JB（[]ai，bi[JB）]]为需求点i所要求服务的时间范围，各个需求点坐标及需求量如表1所示；各个社区蔬菜直销点的服务时间范围如表2所示。

以表1和表2的数据为基础，根据CVRP问题选址模型编写Lingo程序，以直销点2作为备选站点为例，求得全局最优距离为20.45203km。同理，分别选取直销点9、直销点15得到全局最优解。其最终结果如表3所示。

从表3可知，依据CVRP问题选址模型，路径长度20.45203（直销点2）>20.39479（直销点9）>20.31292（直销点15）。因此，应当选择直销点15作为配送站点为乌鲁木齐市社区蔬菜配送直销点进行配送作业。

因此，根据CVRPTW问题选址模型编写程序，以直销点2作为备选站点为例，同样可求得全局最优总距离为30.34672km。同理，分别选取直销点9、直销点15得到全局最优解。最终结果如表4所示。

从表4可知，依据CVRPTW问题选址模型，路径长度30.34672（直销点2）>28.56790（直销点15）>27.91033（直销点9），所以，应当选择直销点9作为配送站点，为乌鲁木齐市社区蔬菜配送直销点进行配送作业。

3 结 论

为了解决城市物流配送站点选址问题，本文从实际出发，构建了考虑容量、时间窗约束的选址模型，采用能够快速求解线性问题的Lingo软件进行求解。结合实例表明，Lingo软件是一种快速有效求解配送站点选址的方法，能够快速求得选址问题最优解。

参考文献：

[1]Angela L.Rademeyer.The Assignment Routing Problem with Nominated Delivery Days（ARPNDD）：Definition and Solution Heuristics [C].University of Illinois Press，2008，pp.1-120.

[2] Swagath Janakiraman.Truck Routing Problem in Distribution of Gasoline to Gas Stations[C].University of The Pennsylvania State，2010，pp.1-94.

[3]谢金星，薛毅.优化建模与Lindo/Lingo软件[M].北京：清华大学出版社，2005（7）.

[4]牛永亮，王金妹.物流配送车辆路线求解算法[J].交通运输工程学报，2006，6（2）：83-87.

[5]徐丽蕊.基于LINGO的城市物流配送路径优化[J].电子设计工程，2013，21（22）：52-54.