考虑随机行驶时间的商贸物流网络设计问题研究

景春光

（交通运输部科学研究院，北京　100029）



考虑随机行驶时间的商贸物流网络设计问题研究

景春光

（交通运输部科学研究院，北京100029）

针对商贸物流网络设计问题，以最小化商贸物流网络构建成本为优化目标，同时决策商贸物流各级配送中心的选址与商贸物流车辆的配送路径。在优化过程中考虑物流车辆行驶时间具有随机特性，以各级配送中心建设成本最小化、物流配送成本期望值最小化为目标，构建了多目标规划模型。选用遗传算法提出了设计模型的求解算法并给出了编码设置，物流配送成本计算等关键步骤设计。最后，采取算例验证了模型与算法的有效性。

运输经济；随机行驶时间；配送中心选址；物流车辆路径；商贸物流；物流网络

1　引言

2014年9月24日，中华人民共和国商务部发布了《商务部关于促进商贸物流发展的实施意见》（商流通函［2014］790号），提出“商贸物流是指与批发、零售、住宿、餐饮、居民服务等商贸服务业及进出口贸易相关的物流服务活动，是整个物流过程中对成本影响比较大的环节，新技术应用和商业模式创新最为集中，作为现代物流的重要组成部分，直接关系到生产资料流通和生活资料流通的顺利运行”。

在满足商贸物流需求的前提下对商贸物流网络体系构建成本最小化，是提升商贸利润的重要手段。因此，如何使商贸物流网络体系构建成本最小化，成为了商贸物流可持续发展的关键环节。商贸物流网络构建成本包含两个方面：各级配送中心的建设成本；各级配送中心之间的物流配送成本。那么，商贸物流网络体系构建成本最小化就等价于综合考虑各级配送中心的建设成本最小化、各级配送中心之间的物流配送成本最小化。

各级配送中心构建可以归属于设施选址问题（Facility Location Problem，FLP）［1］。设施选址问题可以分为连续设施选址问题［2-3］（Continuous Facility Location Problem）与离散设施选址问题（Discrete FacilityLocation Problem）［4-6］。本文的配送中心选址问题属于离散设施选址问题。物流配送成本由配送车辆路径决定，归属于车辆路径问题（Vehicle Routing Problem，VRP），最早由Dantzig和Ramser［7］于1959年提出，该问题可定义［8］为：对于一系列装货点和（或）卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件下（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等），达到一定的目标（如路程最短、费用最少、时间尽量少、使用车辆数尽量少等）。VRP问题一直是学者们研究的热门问题［9-11］。

在物流配送系统中，配送中心选址问题与在此基础上的车辆路径问题相互影响［12］，可以同时决策设施选址问题与车辆路径问题。文献［13］研究了竞争环境下截流设施选址与带时间窗的多中心车辆路径问题。文献［14］构建了报废汽车回收物流网络选址－路径优化模型，旨在解决拆解中心选址问题、中转场选址问题、拆解中心和中转场的建设数目以及车辆路径问题。在文献［12-14］中物流车辆的行驶时间均为固定时间。在实际过程，给定距离下物流车辆的行驶时间具有不确定特性。不确定行驶时间具有随机行驶时间、模糊行驶时间等多种形态，本文将研究物流车辆行驶时间为随机时间的情况，其他类型的不确定行驶时间可以通过扩展本文方法进行研究。综上，本文将研究随机行驶时间下商贸物流网络设计问题，同时优化商贸配送中心选址与商贸物流配送的车辆路径。

2　问题分析

商贸物流网络结构示意如图1所示。整个商贸物流服务范围被划分为若干个服务区域，每一个区域由相应的各级物流配送中心构成。图1中商贸物流的服务范围被划分为A1、A2、A3、A44个服务区域，每一个服务区域内存在1级配送中心与若干个2级配送中心，由1级配送中心向本服务区域的所有2级配送中心运输商贸货物，例如A1服务区域中存在1级配送中心B1与6个2级配送中心（A1-1、A1-2、A1-3、A1-4、A1-5、A1-6），由B1向A1-1、A1-2、A1-3、A1-4、A1-5、A1-6配送商贸货物，经过优化后配送路径为B1→A1-1→A1-2→A1-3→B1、B1→A1-4→A1-5→A1-6→B1，共需要两辆配送车辆。商贸物流网络结构可以应用于零售、餐饮等多个领域，例如应用于餐饮时1级配送中心B1与6个相应的2级配送中心（A1-1、A1-2、A1-3、A1-4、A1-5、A1-6）可分别对应餐饮原料配送中心与固定的餐饮店面。在本文的后续研究中，采取1级、2级配送中心的模式（1个1级配送中心与若干个2级配送中心），可以通过增加配送中心等级的形式将本文方法扩展应用到结构更复杂的商贸物流网络设计研究中，例如1级配送中心→2级配送中心→3级配送中心的商贸物流网络结构形式。

图1　商贸物流网络示意图

商贸物流网络设计的流程包含以下几个主要步骤：

（1）将服务范围划分若干个服务区域，服务区域界限即可以与所在县市的行政区域保持一致，也可以按照街道、居住小区、商圈的方式进行划分；

（2）在服务区域划定后，在每一个服务区域内构建1级、2级配送中心的候选地址集合；

（3）预测2级配送中心点的商贸物流需求；

（4）构建不同的1级、2级配送中心的组合方案，并确定该组合方案下的物流配送路径；

（5）计算每一个组合方案的配送中心建设成本与物流配送成本，经过比选确定最优方案。

3　数学模型构建

当物流车辆行驶时间具有随机性且分布概率已知时，每一个行驶时间对应一个情景s。在随机环境中，每一个情景对应着一个固定的物流车辆行驶时间，情景s可以看作是未来不确定因素的某一种实现，或对不确定因素在未来时间段演化情况的一种描述［15］。

3.1优化目标

按照上节分析，商贸物流网络设计将首先划定若干服务区域，那么该问题就变为针对每一个服务区域决策1个1级配送中心和若干个2级配送中心的选址，并决定1级配送中心至所有2级配送中心的物流配送路径。本节针对给定的服务区域建立数学模型，决策该服务区域内1级与2级配送中心的选址及物流车辆路径，建模的优化目标为1级与2级配送中心的建设成本、物流配送成本。物流配送成本一般与运输时间或距离成正比，本文选用物流配送时间衡量物流配送成本。综上，优化目标为1级与2级配送中心的建设成本、物流车辆的总行驶时间。

3.2模型假设

（1）1级、2级配送中心的选址候选集合已知；

（2）2级配送中心需要修建的数量已知；

（3）2级配送中心所需的物流需求已知，该需求为固定需求；

（4）物流车辆行驶时间具有随机特性，且概率密度函数已知；

（5）所有配送均采取相同类型的物流配送车辆。

3.3变量说明

M—1级配送中心的选址候选位置集合；

N—2级配送中心的选址候选位置集合；

S—情景s集合，每一个情景s对应一个固定的物流车辆行驶时间；

δ（s）—情景s的概率密度函数；

tijs—情景s下从配送中心i与配送中心j之间的物流车辆行驶时间，其中s∈S，i、j∈M∪N且i≠j；

dn—2级配送中心建设在位置n时需要的配送需求量，该需求量可以通过调研位置n服务范围内现有与潜在商贸物流企业获得，n∈N；

qm—1级配送中心在位置m上建设时的建设成本，m∈M；

pn—2级配送中心在位置n上建设时的建设成本，n∈N；

ω—2级配送中心的建设数目；

K—物流配送车辆集合；

g—单辆配送车辆所能承载的最大容量；

κ—2级配送中心需要服务的最小物流需求；

xm—0-1决策变量，当xm=1时在位置m上建设1级配送中心，否则xm=0，m∈M；

yn—0-1决策变量，当yn=1时在位置n上建设2级配送中心，否则yn=0，n∈N；

zijk—0-1决策变量，当车辆k从配送中心i直接到达配送中心j时为1，否则为0，其中i、j∈M∪N且i≠j；

3.4多目标规划模型

其中，式（1）为目标函数，表示配送中心的建设成本、物流配送成本（物流车辆总营运时间）最小化，β1与β2分别是多目标权重系数，且β1+β2=1。约束（2）表示每一个2级配送中心只被一辆物流配送车辆送货服务。约束（3）为流量守恒约束，进入配送中心的配送车辆数量与离开配送中心的配送车辆数量相当。约束（4）为物流配送车辆的容量限制约束。约束（5）表示建设的2级配送中心需要满足一定规模的物流需求。约束（6）、约束（7）为逻辑约束，表示只有配送中心被建造时它才能被配送车辆服务。约束（8）表示2级配送中心的建设数量约束。约束（9）、（10）、（11）为0-1变量逻辑约束。

4　求解算法设计

4.1算法整体描述

按照上文分析，商贸物流网络设计问题被分解为设施选址问题与车辆路径问题，这两个问题均可以用遗传算法（Genetic Algorithm，GA）有效求解［16-17］。选用遗传算法进行求解设计。由于车辆路径优化方案依托于配送中心选址方案，因此针对每一个配送中心选址方案都要决策其车辆路径优化方案才能计算目标函数（式（1））。将整个商贸物流网络设计的算法简称为NDPGA，给定配送中心选址方案下求解配送方案的子算法简称为VRP-GA。整个求解算法步骤如图2所示，NDP-GA的染色体适应度按照式（1）计算。

图2　算法计算流程

4.2NDP-GA关键步骤设计

（1）染色体编码设计。决策变量xm、yn均为0-1整数变量，染色体编码选用0-1编码的形式，每一个配送中心候选位置对应一个染色体编码，当染色体编码为1时表示该位置上被建设相应级别的配送中心，为0表示不建设。图3为具体示例，1级配送中心候选位置有4个，2级配送中心候选位置有8个，解码表示：在位置2修建了1级配送中心、在位置7/9/10/12修建了2级配送中心。

图3　NDP-GA编码设计示意

（2）选择、交叉与变异操作。选择操作采取轮盘赌的形式。交叉操作为了保持染色体的可行性（1级配送中心数量为1个，2级配送中心建设数量为ω个），在进行交叉操作时交换两个染色体全部xm编码，交换yn相同位置的基因，判断2级配送中心的建设数量是否为ω个，如果不是，对染色体的yn编码进行修正。交叉算子采取单点变异算子操作，随机选择两个位置的基因（要么都是xm的编码，要么都是yn的编码）进行交换，同样需要判断2级配送中心的建设数量是否为ω个，如果不是，对染色体的yn编码进行修正。

4.3NDP-GA关键步骤设计

（1）染色体编码设计。染色体编码选取整数编码的形式，表示物流车辆按照次序服务的2级配送中心序列，-1表示1级配送中心，其他正数表示相应的2级配送中心序号。例如，编码（-1，1，4，5，-1，6，3，2，-1）解码后表示有两辆车配送，车辆1依次对2级配送中心1、4、5进行配送服务，车辆2依次对2级配送中兴6、3、2进行配送服务。

（2）物流配送成本计算。物流配送成本由物流车辆总运输时间表示，而物流车辆行驶时间具有随机特性，因此采用随机模拟的方式计算物流配送成本。首先，设定生成情景样本的数量为ξ。接着，根据随机车辆运营时间的概率分布模拟生成ξ个情景，计算每一个情景s下的物流车辆总运输时间。最后，选用文献［18］的方法，假设所有情景s发生的概率均相同，计算物流车辆总运输时间F2，具体公式如下：

5　算例分析

算例包含12个结点，其相互位置关系如图4所示。其中，结点1-3为1级配送中心候选地址，结点4-12为2级配送中心候选地址。表1为各结点之间的物流车辆行驶时间，设定随机运输时间符合正态分布，表中数据格式为（μ，σ），μ，σ分别表示物流车辆行驶时间的均值与方差。表2为各位置配送中心的建设成本与运输需求。ω取6，出于2级配送中心均匀分布的考虑，限定结点4、5、6至少要建造2个2级配送中心，结点7、8至少要建造1个2级配送中心，结点9、10至少要建造1个2级配送中心，结点11、12至少要建造1个2级配送中心。2级配送中心需要服务的最小物流需求κ为11.5t。单辆物流配送车辆所能承载的最大容量g取7t/车。NDP-GA染色体种群设定为50个，交叉概率与变异概率各为0.6、0.15，最大迭代计算次数为300次。VRP-GA染色体种群设定为80个，交叉概率与变异概率各为0.7、0.2，最大迭代计算次数为500次。

式（1）的多目标权重系数β1与β2取多组值进行计算，分别是β1=0.9、β2=0.1，β1=0.7、β2=0.3，β1=0.4、β2= 0.6，β1=0.1、β2=0.9。优化结果见表3。图5为β1=0.9、β2=0.1时的迭代曲线，算法在63次迭代后计算获得最优值，验证了设计算法的有效性。从表3中可以看出，随着不同β1与β2的组合，优化结果不同，随着β1的降低、β2的升高，优化结果更偏向于选择运输成本更低的方案。

表1　结点之间的随机行驶时间（h）

表2　结点的配送中心建造成本与物流需求

表3　优化结果

图4　算例示意图

图5　当β1=0.9、β2=0.1时的迭代曲线

6　结语

商贸物流是我国物流未来发展的重要方向。本文研究商贸物流网络设计问题，将该问题拆解为配送中心选址决策与物流配送路径决策。基于物流车辆行驶时间具有随机特性，将该变量设置为随机变量，以各级配送中心建设成本最小化、物流配送成本期望值最小化为目标，构建了多目标规划模型。结合遗传算法给出了求解模型的求解步骤，并给出了编码设置、物流配送成本计算等关键步骤设计。通过算例验证了本文模型与算法的有效性。

［1］秦进.多商品物流网络设计相关优化模型及算法研究［D］.长沙：中南大学，2006.

［2］Durmaz E，Aras N，Altinel I.Discrete approximation heuristics for the capacitated continuous location-allocation problem with probabilistic customer locations［J］.Computersamp;Operations Research，2009，36（7）：2 139-2 148.

［3］Dinler D，Tural M K，Iyigun C.Heuristics for a continuous multi-facility location problem with demand regions［J］.Computersamp;Operations Research，2015，62：237-256.

［4］Harkness J，ReVelle C.Facility Location with Increasing Production Costs［J］.European Journal of Operational Research，2003，145（3）：1-13.

［5］Wu T H，Lin J N.Solving the competitive discretionary service facility location problem［J］.European Journal of Operational Research，2003，144（2）：366.378.

［6］Murat A，Laporte G，Verter V.A global shooting algorithm for the facility location and capacity acquisition problem on a line with dense demand［J］.Computersamp;Operations Research，2016，71：1-15.

［7］Dantzig G，Ramser R.The truck dispatching problem［J］.Management Science.1959，（6）：80-91.

［8］李军，郭耀煌.物流配送车辆优化调度理论与方法［M］.北京：中国物资出版社，2001.

［9］Scheuerer S.A tabu search heuristic for the truck and trailer routing problem［J］.Computersamp;Operations Research，2006，33：894-909.

［10］Avci M，Topaloglu S.A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery［J］.Expert Systems with Applications，2016，53（1）：160-171.

［11］Figliozzi M A.The time dependent vehicle routing problem with time windows：Benchmark problems，an efficient solution algorithm，and solution characteristics［J］.Transportation Research Part E：Logistics，2012，48（3）：616-636.

［12］曾庆成，杨忠振，蒋永雷.配送中心选址与车辆路径一体优化模型与算法［J］.武汉理工大学学报（交通科学与工程版），2009，33（2）：267-270.

［13］王道平，徐展，杨岑.基于竞争环境的截流设施选址与车辆路径问题［J］.控制与决策，2015，30（6）：1 054-1 058.

［14］贺政纲，邹晔，杨晓.报废汽车物流网络选址-路径问题建模与求解算法研究［J］.公路交通科技，2016，33（3）：138-145.

［15］张人千，王如平.随机能力规划的Scenario模型及其决策风险分析［J］.系统工程理论与实践，2009，29（1）：55-63.

［16］Fernandes D R，Rocha C，Aloise D，Ribeiro G M，Santos E M，Silva A.A simple and effective genetic algorithm for the twostage capacitated facility location problem［J］.Computersamp; Industrial Engineering，2014，75：200-208.

［17］Razali N M.An Efficient Genetic Algorithm for Large Scale Vehicle Routing Problem Subject to Precedence Constraints［J］. Procedia-Social and Behavioral Sciences，2015，195（3）：1 922-1 931

［18］Yin Y F，M Madanat S，L X Y.Robust improvement schemes for road networks under demand uncertainty［J］.European Journal of Operational Research，2009，198（2）：470-479.

Study on Trade Logistics Network Design with Stochastic Traveling Time Consideration

Jing Chunguang
（China Academy of Transportation Sciences， Beijing 100029， China）

In this paper， in view of the issues in the design of the trade logistics network and with the minimal network establishmentcost as the target， we attempted to finalize the location of the various levels of distribution centers on the network and the running route of thelogistics vehicles. During the optimization process， we considered the stochasticity of the traveling time of the logistics vehicles andestablished the programming model targeting at minimizing the total distribution center construction cost and the expected logisticsdistribution cost. Then we adopted the genetic algorithm to solve the model and presented the programming and calculation steps. At the end，through a numerical example， we demonstrated the validity of the model and algorithm.

transportation economy； stochastic traveling time； location allocation of distribution center； routing of logistics vehicle；trade logistics； logistics network

F224；F253.9

A

1005-152X（2016）08-0064-06

10.3969/j.issn.1005-152X.2016.08.018

2016-07-04

景春光（1976-），男，山东东营人，高级工程师，研究方向：交通规划。