物流运输优化问题的线性规划模型构建

杨自辉 ，符 卓

（1.中南大学 交通运输工程学院，长沙410075；2.长沙师范学院，长沙 410100）

0 引言

车辆路径问题是一个非常有挑战性的组合优化问题，合理的车辆路径规划，能有效地降低服务商运作成本，提高服务质量，因此车辆调度优化问题很快成为研究的热点。多式联运的车辆运输问题属于典型的多目标函数优化问题——既要追求经济实惠，又要力保高效迅速。

王凤洲等（2005）认为多式联运系统是基于系统整合观和供应链思想以及现代信息技术的多种运输方式的最佳组合，具有自身的特点和独特的系统特征,相对于传统的运输模式来说,是一个革命性的突破,从根本上区别于传统的物质运输模式。蒋洋等（2012）提出了针对“多式联运运输方案选择问题”的一种全新的交叉熵算法,并据此给出了相应的计算方法。采用具有节点扩展特性的“网络图”对多式联运网络进行详细的描述,进而转化为“最短路问题”进行求解。结果显示,运输成本、转运费用对运输方案具有很重要的决定作用,并且提出的交叉熵算法具有很快收敛的性质。冯芬玲,张清雅（2012）综合考虑环境污染等诸多因素对“多式联运”可持续发展的影响效应,引入多式联运社会总成本的概念,以“多式联运社会总成本最小化”为整体优化目标,建立多式联运运输方式协同优化模型。分别采集并处理各种运输方式的运输、污染、能源及安全成本数据和运输数据,并利用模糊综合评价法确定各个成本的影响权重。结果显示：在对多式联运进行决策制定时,应综合考虑多式联运的影响因素,选择合理的运输方式。马彩雯,孙光圻（2006）为了在国际多式联运信息集成的基础上,实现对国际多式联运的运输组织过程的集成管理和协同运作，利用Agent技术,运用一种面向对象的新方法,设计了国际多式联运“虚拟企业”的信息集成框。孙彬，陈秋双（2013）针对多式联运运输决策中的特点,提出一种基于多Agent的多式联运承运人选择和路径优化方法。结果表明,这一引导机制可以有效加快协商过程的收敛性。雷定猷等（2014）基于可行性与合理性的角度,分析了长大货物多式联运路径优化的影响因素。以“运输时间最短”、“里程与费用最少”为目标函数,以“线路限界、桥梁承载能力、起重设备的起重能力”为约束条件,建立了长大货物多式联运路径优化原始模型。考虑了约束条件的改造性特征,将原始模型扩展优化,设计了二维序列编码策略,运用遗传算法求解扩展模型。

纵观现有文献，对于多式联运运输优化问题的探讨中，并没有考虑“时间成本”的存在带来的影响，这样的分析会带来一定的计算误差。在本文所构建的模型中，创造性地通过“权重系数”的衔接，引入“时间成本”的思想，将“时间”量化为“成本”，使得“多决策目标的优化问题”转化为“古典线性背景下的优化决策问题”。

1 问题的叙述与分析

1.1 问题的一般化叙述

一般化的“物流配送路径优化”问题可以进行这样的表述：从物流配送的中心点（又称为“物流节点”）向多个顾客（又称为“需求点”）用多辆汽车（决定了本文分析的“路径数”）送货。

限制条件为：（1）每辆汽车的载重能力是一定的；（2）具有一定的需求量和需求点位置。

规划目标：安排合理的汽车路线图，使运输总距离最短，运输花费的总运费最小，并满足以下限制条件：(1)每个需求点的需求必须满足；(2)缩短配送时间，降低配送成本。

图1 整车物流运输方式

1.2 问题分析

本问题属于典型的多目标函数优化问题——既要追求经济实惠，追求成本最小化；又要力保高效迅速，追求时间最小化。目标函数的要求给模型的求解增加了难度，通过一个“时间成本转换因子”，将时间转化为成本，这样就把原来的多目标函数优化问题转化为单目标函数优化问题了。

（1）运输资源使用最合理：为了充分运用现有运力资源，物尽其用，而不利用资源体系外的另外车辆，在运力非常紧张、运力与成本或效益有一定相关性的情况下，也可以将运力安排为目标，确定配送路线。

（2）运输总路程最短：如果运输成本和路程长短具有较强的相关性，而和其他因素相关性不强时，我们在进行决策时可以选择“运输总路程最短”为决策目标。

（3）运输活动获得的效益最高：在运输的实际问题中，我们常常以“企业当下的效益情况”为主要制约因素，同时要考虑到“企业的长远发展”。

（4）时间效率最高：有时在实际问题的决策过程中，很难同时考虑到“成本”的问题，甚至需要牺牲其余各项成本来满足“时间效率最高”的苛刻要求，当然，考虑到实际决策问题的制约因素，对“时间效率最高”的要求必须建立在“控制成本最低”的基础上。

（5）运输消耗的成本最低：在实际计算过程中，成本的计算并不太容易，但和“以运输效益为最终决策目标”相比可以简化问题，采用“最低成本”为决策目标相当于选择了以“效益最高”为决策目标。

2 物流运输优化问题的线性规划模型的建立

2.1 模型的一般描述

假设有一个“多式联运运输方式”选择为具有多个决策目标的优化问题，我们将研究的问题一般化，具体叙述如下：

运输一批货物，起始地记为O，目的地记为P，途径的城市个数为n（n＞2），把两个城市算作一个“城市对”，那么，每个城市对之间可供选择的运输方式有m（m＞1）种，根据排列组合的原理，可知一共有mn-1种交通组合方式。对于这些交通组合方式，如果两城市间是相邻的，那么所有运输方式的时间以及费用都是不相同的，我们还假设当从某一种运输方式转变到另一种运输方式时，需要消耗一定的中转时间和费用。所以，可以知道本研究问题的关键是明确如何选择运输方式，实现以下两个决策目标：（1）运输费用总成本最小；（2）运输消耗时间最短。

我们用一个虚拟的“运输网络图”对上述一般化的问题进行具体描述，见图2所示：

图2 物流运输问题的多式联运描述图

（1）设始发点为O，终点为P，从事发点到终点途径的各个城市分别扩展为n个城市节点，如图所示，任何两个物流节点之间有m种运输方式，故在此可以假设每个节点有m条运输线路流入，也有m条运输线路流出。如对于节点A，其左侧有1个节点O，即物流中心或配送中心，共有n种运输方式输入节点，故将A虚拟成m个节点，每个节点分别代表一个流入，同理A右侧也有m个节点，A21、A22、A23、…、A2m、分别表示m种运输方式输出节点。同理可以将其他物流节点也类似虚拟。

（2）相关符号表示的含义叙述如下：

q：货物从城市i到城市i+1，选择第k种运输方式的运输量；

W：综合考虑运输时间和运输成本时，运输时间对运输成本的单位时间费用权重调整值。

（3）I表示所有要经过的城市的集合。

2.2 物流运输优化问题的线性规划模型

在我们上面讨论的“多式联运运输方式选择多决策目标的优化问题”中，其目标是要降低运输总费用，故该问题的线性规划模型为：

3 结论及模型的推广应用

在解决多目标函数问题时，通过“时间成本转换因子”将“具有多个决策目标的优化问题”转换为“经典的只有单一决策目标的线性规划问题”，解决了具有多个决策目标优化问题在模型设定时的难点，将模型的决策目标、约束条件一般化、线性化，由此大大降低了模型在求解过程中的难度。本模型的创新之处主要在于提供一种将时间转化为成本的思想，将“决策目标多样化的优化问题”转化为“经典的只有单一决策目标的线性规划问题”。本文讨论得出的模型可以应用于各类关于“多式联运运输优化问题”的探讨和优化。当然，在模型的实际应用中可视实际情况对于目标函数以及约束条件加以修改限制，用来求解企业实际需要的运输优化问题。

[1]孙彬，陈秋双.基于多Agent的多式联运运输决策与动态协调[J].计算机集成制造系统，2013，（12）.

[2]雷定猷,游伟,张英贵,皮志东.长大货物多式联运路径优化模型与算法[J].交通运输工程学报，2014，（1）.

[3]马彩雯,孙光圻.基于多Agent的国际多式联运“虚拟企业”信息集成框架[J].大连海事大学学报，2006，（2）.

[4]王凤洲，陆晓倩，吴秋明.基于系统整合观的多式联运系统特征分析[J].系统辩证学学报，2005，（4）.

[5]冯芬玲,张清雅.基于环境的多式联运运输方式协同组织优化模型[J].铁道科学与工程学报，2012，（6）.

[6]蒋洋，张星臣，王永亮.多式联运运输方案选择的交叉熵方法[J].交通运输系统工程与信息，2012，（5）.