基于价值函数的运输规划模型设计

夏贤康，卢星儒XIA Xian-kang, LU Xing-ru（兰州交通大学 交通运输学院，甘肃 兰州 730070）(School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou 730070, Gansu, China)

基于价值函数的运输规划模型设计

夏贤康，卢星儒
XIA Xian-kang, LU Xing-ru
（兰州交通大学 交通运输学院，甘肃 兰州 730070）
(School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou 730070, Gansu, China)

在阐述运输规划模型建模思路和算法的基础上，针对物流网络中的运输配送问题对运输规划模型进行设计，通过引入价值函数，构建运输品类数量和到达时间价值函数的双层目标规划模型，采用遗传算法对上述模型的最优近似解进行求解。经过实例分析，根据各需求点运输品类需求情况计算各个需求点之间的行驶时间及各条路线到达需求点的时间，得到相应的最佳运输路线，结果表明该算法可行。

运输规划；价值函数；遗传算法

随着经济全球化的发展，不同形式、不同层次的区域物流和国际物流等逐渐发展起来，迫切需要一种高效完善的物流网络系统作技术支撑。物流企业需要在全球范围内建立物流网络系统，实现对整个物流网络的效用最高和总费用最低的优化，运输配送作为物流网络的中心环节，对运输规划模型进行设计是物流网络优化的重点，考虑在价值函数理论的基础上，对以运输量和到达时间为双目标的运输规划问题进行研究[1-4]。

1 建模与算法设计

1.1 建模思路

（1）运输路网。假设配送中心 A = {A1，A2，…，Ah} 为运输出发点，目标地点为需求点 B = {B1，B2，…，Bn} ，根据需求点 B、配送中心 A、运输车辆的运输路网结构可以列出所有运输线路，如表1所示。其中，序号栏 lj 表示路径分类，设置 A 为出发点，运输路径可以用 lj×md 维的 0-1 矩阵 A 来表示路径情况。当 A 中元素 ali= 1 时，表示 lj条线路经过需求 Bi；当 ali= 0 时，则 lj 条线路不经过需求点 Bi。

表1 运输路线示意表

（2）待运输的物资。假设有 t 种物资要运输到需求点，分别记为 m = 1，2，…，t。设配送中心 Al关于物资 t 的储备总量为 clt，其中 l = 1，2，…，mc，mc 为 t 种物资的储备总量。

（3）运输工具。假设有 r 辆运输车辆可以进行物资运输，分别记为 k = 1，2，…，r，trk为 k 的装载能力。假设在线路不发生堵塞的情况下，所有运输工具的运输效率相同，并且行驶速度也相同，则可以用lj×md 维实数矩阵 TS 来表示全部路径上的运输时间。TS 中的元素表示第 lj 条线路到达需求点 Bi的时间，tsli∈ [0，mt]，当 ali= 0 时，tsli= mt，mt 为运输时间的极大值。

（4）决策变量。χ，y，z 分别为双目标运输规划的决策变量，χki为运输工具 k 运输到需求点 Bi的物资数量；yk∈ [1，2，…，lj] 为整数，表示 k 选表1 中第 lj 条线路；zk∈ [1，2，…，t] 为整数，表示 k承担第 t 种物资的运输。

1.2 模型构建

模型的目标函数为需求点的价值函数之和最大，然后根据路径是否拥堵、运输资源、运力、单一物资单一路径等限制设置约束条件。以运输时间和运输费用价值最大为目标建立双目标规划模型[5]，将不同的应对资源同时进行运输规划，该模型计算公式为

式中：vdi为需求点的子任务价值函数之和；vDi,m() 为运输品类 m 运送到需求点 Bi的时间价值函数，⑵式为需求点 Bi的价值函数之和，其中vDi,m() 的具体内容根据需求点价值函数的约束条件确立；⑶ 式中 χsmi,d表示不同运输工具 k 运输 m 类物资到需求点的时间价值；⑷ 式用于计算同一时间段内到达需求点 Bi运输品类 m 的数量；trk表示 k 的运力；cml为需求点 Bi可用物资 m 的总量；⑹ 式中 ayki为决策变量，表示只有当路径 l 经过需求点 Bi时，才会在 Bi处卸下物资；yk∈ [1，2，…，lj] 表示 k 选择的路线；zk∈ [1，2，…，t] 表示 k 装载的运输品类类型。

2 模型近似解的遗传算法

采用遗传算法对上述模型的最优近似解进行求解，算法步骤如下[5-10]。

步骤 1：生成初始染色体，将满足上述模型的约束条件的染色体转换为变量 (χ，y，z)。

步骤 3：选择运算，选出满足条件的染色体。

步骤 4：交配运算，按照上述模型的约束条件进行交配，选出符合条件的染色体。

步骤 5：变异运算，按照上述模型的约束条件进行变异，选出符合条件的染色体。

步骤 6：使用步骤 2 中的适应性指标计算新一代染色体的适应性。

步骤 7：按照给定的循环次数循环步骤 3—步骤6，按照给定的循环次数进行迭代。

步骤 8：输出结果，选出适应性指标最好的染色体转变为最优解，输出 χ，y，z，(vd1，vd2，…，vdmd)。

根据以上算法，运用 Matlab 软件计算得到上述模型的近似最优解，根据输出的 (χ，y，z) 可以得到运输工具的路径选取及各个需求点的运送物资量。

3 实例分析

假设有 7 个需求点，分别记为 B1，B2，…，B7，各个需求点需求量为不确定变量，其数值按无量纲化进行处理，需求情况如表2 所示，一个配送中心记为 A，运输物流网络如图1 所示。

根据相关部门的统计数据，计算各个需求点之间的行驶时间 TS 如表3 所示。根据图1的运输物流网络整理得到 6 条运输路线，分别为①A→B6→B7；②A→B6→B5→B4→B3→B1；③A→B6→B5→B4→ B2；④A→B3→B4→B5→B6→B7；⑤A→B3→B4→B2；⑥A→B3→B1。根据得到的运输路线结合表3 的行驶时间，可以得出每条线路经过各需求点的时间，如表4 所示。

表2 各需求点运输品类需求情况

图1 运输物流网络图

表3 各个需求点之间的行驶时间

表4 各条路线到达需求点的时间

假设配送中心的物资量为 10，品种为单一物资，而且只有 4 辆运输车可供使用，每辆车的最大载货量为 2。采用决策变量 χli表示第 l 条路线送至需求点 Bi的物资量，则需求点 Bi的价值函数计

算公式[11]为，其中 v (χ) =则运输任务的价值函数为 v =采用 Matlab 软件计算上述模型的近似最优解，根据输出的 χ 可以得到最优近似解，最佳运输路线选取②、③、④、⑤，根据输出的 y 和 z 可以得到各需求点接收运输品类数量如表5 所示，最优价值函数为 3.96。

表5 各需求点接收运输品类数量

4 结束语

以整体价值最大化为目标来构建运输规划模型，不仅可以满足不同客户需求，而且在提高运输效率的同时能够降低企业成本[12]。该模型在一般物流配送网络中应用良好，为解决该类运输问题提供了可借鉴的思路，同时也为处理多配送点的复杂网络设计提供了相应的理论支持。另外，该模型还适用于销售高峰期物流中心向各分销点配货的紧急情况[13]，通过进一步优化模型，尽可能全面地考虑影响因素，从而提出更加合理的运输优化方案。

[1] 于 锐，曹介南，朱 培. 车辆运输路径规划问题研究[J]. 计算机技术与发展，2011，21(1)：5-8. YU Rui，CAO Jie-nan，ZHU Pei. Study on Vehicle Path Planning Problem[J]. Computer Technology and Development，2011，21(1)：5-8.

[2] Amos T，Daniel K. Advance in Prospect Theory：Cumulative Representation of Uncertainty[J]. Journal of Risk and Uncertainty，1992(5)：297-323.

[3] Saber H M，Ravindran A. Nonlinear Goal Programming Theory and Practice：A Survey[J]. Computers and Operations Research，1993(20)：275-291.

[4] 田 青，缪立新，郑 力. 基于运输规划和组合GA 的基本物流网络设计[J]. 清华大学学报(自然科学版)，2004，44 (11)：22-23. TIAN Qin，LIAO Li-xin，ZHENG Li. Logistics Network Design based on Transport Planning and Combined GA[J]. Journal of Tsinghua University (Natural Science Edition)， 2004，44(11)：22-23.

[5] 王连锋，宋建社，曹继平，等. 带硬时间窗模糊车辆路径问题的多目标优化[J]. 计算机工程，2013，39(4)：9-17. WANG Lian-feng，SONG Jian-she，CAO Ji-ping，et al. The Multi-objective Optimization Fuzzy Vehicle Routing Problem with Hard Time Windows[J]. Computer Engineering，2013，39(4)：9-17.

[6] 刘宝碇，赵瑞清，王 纲. 不确定规划及应用[M]. 北京：清华大学出版社，2003. LIU Bao-ding，ZHAO Rui-qing，WANG Gang. Uncertain Programming and Application[M]. Beijing：Tsinghua University press，2003.

[7] 张 潜，高立群，胡祥培. 集成化物流中的定位运输路线安排问题(LRP)优化算法评述[J]. 东北大学学报(自然科学版)，2003，24(1)：31-34. ZHANG Qian，GAO Li-qun， HU Xiang-pei. Integrated Logistics Location Routing Arrangement Problem (LRP) Optimization Algorithm Review[J]. Journal of Northeastern University (Natural Science Edition)， 2003，24 (1)：31-34.

[8] 王绍仁，马祖军. 震害紧急响应阶段应急物流系统中的LRP[J]. 系统工程理论与实践，2011，31(8)： 1497-1507. WANG Shao-ren，MA Zu-jun. Earthquake Disaster Emergency Response in the Stage of Emergency Logistics System LRP[J]. Theory of System Engineering and Practice，2011，31 (8)：1497-1507.

[9] 汪传旭，邓先明. 模糊环境下多出救点应急救援车辆路径与物资运输优化研究[J]. 系统管理学报．2011，20(3)：269-275.

(  )(  )WANG Chuan-xu，DENG Xian-ming. Multi-depot Emergency Vehicle Routing and Transportation Optimization with Fuzzy Variables[J]. Journal of Systems & Management，2011，20(3)：269-275.

[10] 邹 彤，李 宁，孙德宝. 不确定车辆数量的有时间窗车辆路径问题的遗传算法[J]. 系统工程理论与实践，2004，24(6)：134-138. ZOU Tong，LI Ning，SUN De-bao. Uncertain Number of Vehicles，Vehicle Routing Problem with Time Windows，Genetic Algorithm[J]. System Engineering Theory and Practice，2004，24 (6)：134-138.

[11] Amos T，Daniel K. Advance in Prospect Theory：Cumulative Representation of Uncertainty[J]. Journal of Risk and Uncertainty，1992(5)：297-323.

[12] Liu B D. Uncertainty Theory：A Branch of Mathematics for Modeling Human Uncertainty[J]. Springer-Verlag，2010(12)：147-152.

[13] 梁强升. 城市轨道交通线路高峰期的不均衡运输组织研究与应用[J]. 都市快轨交通，2014，27(4)：30-34. LIANG Qiang-sheng. The Unbalanced Transportation Organization Research and Application of the Peak of the City Rail Transit Line[J]. Urban Rapid Rail Transit，2014，27(4)：30-34.

责任编辑：吴文娟

Design of Transportation Planning Model based on Cost Function

Based on expounding the modeling idea and algorithm of transportation planning model, targeting with the problems of transport delivery in logistic network, the transportation planning model is designed, and then, a bi-level objective model combined with category number of transport products and cost function of arrival time is established and the optimized approximate solution of the model is solved by using genetic algorithm. Through example analysis, according to demand status of transport product category in each demand point, the running time among each demand point and the time of each line arriving the demand point are calculated, then relative optimum transport route is achieved, so the study result shows this calculation method is feasible.

Transportation Planning; Cost Function; Genetic Algorithm

1003-1421(2016)07-0053-04

：U294.1；U116.2

B

10.16668/j.cnki.issn.1003-1421.2016.07.10

2015-10-20

2016-03-16

甘肃省自然基金项目 (1506RJZA079)