论文部分内容阅读
【摘要】针对综合运输网络中干线运输和末端配送的分离问题，本文将两者综合考虑，统一用双层规划模型表达。上层规划优化物流总成本，下层规划考虑客户配送成本最小化。采用遗传算法求解该双层模型，实例计算结果验证了该模型的可行性和求解方法的高效性。
【关键词】综合运输；网络优化；车辆路径问题；双层规划；遗传算法
随着物流行业的不断飞速发展，多种运输方式被集成在一起共同发挥作用，综合运输体系不断完善，多式联合运输已经成为我国乃至国际物流及运输业发展的趋势。在整个物流环节中，从货品出发的源头开始，干线运输方式的选择、运输线路的优化以及末端配送的方案都是联合运输中的主要内容。在干线运输环节，公路、铁路、水运等运输方式都已发挥了重要作用，综合交通体系在国内和国际多个层次已经逐渐形成。
在干线运输环节的优化问题，包括两个方面，运输方式的选择和运输路径的优化，而两个问题又是相互影响的，因此本文合并为多种运输方式的联合运输优化问题。在这一方面已经有所研究。已有的文献大多是以运输时间长度、运输成本费用或者服务水平中的一个或多个作为研究目标进行最小化求解，建立联合运输路径的选择与优化的模型。魏际刚等对多式联运中系统协调问题进行了研究，提出了布局、结构、信息等5个方面的问题。刘舰等建立了基于综合运输成本最小和运输风险最小的多目标综合优化模型，孙华灿等建立了一个含路径合理性约束的联合运输路径优化模型。
在配送环节，一般定义为车辆问题（Vehicle Routing Problem，简称VRP）。蒋忠中等并采用模糊数表示车辆行驶时间和顾客服务时间的不确定性，建立了VRP的模糊规划模型；贺国先在满足车辆满载约束的同时充分考虑货物的运到期限，继而建立配送方案模型。求解配送路径优化问题的方法很多，常用的有旅行商法、动态规划法、节约法、扫描法以及蚁群算法、遗传算法和禁忌搜索等人工智能方法。
作为一个整体的物流过程，运输和配送都是不可缺少的，而且两者之间也是相互影响和作用的，上述文献中大多数只考虑了其中某个环节，问题设定有一定的缺陷性。基于此本文将干线运输的综合运输方式优化选择和车辆路径问题综合考虑，建立一个统一的模型研究该问题，将运输费用、中转费用、运输时间、配送费用等作为总成本联合优化。同时考虑到问题的复杂性，本文引入双层规划问题求解该模型，在优化物流成本的同时也充分考虑了用户配送选择问题。
1.综合运输问题
物流过程中综合运输方式完成一次运输任务的过程中，可包括任何两种方式之间的转换，即公-铁、公-水、水-铁、水-公、铁-水、铁-公。由于不同运输方式之间相对独立，运输方式的转换仅发生在枢纽点，不是任意位置。
一般来讲，物流过程都是以公路运输开始，以公路运输结束。但根据物流业务的不同，两头的公路运输过程可能有所差异，可能是直送，也可能是配送。为不失一般性，本文假定开头的一段公路运输过程，是直送，结尾的一段公路运输，是配送过程。配送过程的优化，就是VRP问题，直送过程，会涉及到运输方式和路径的选择，同中间环节的铁路运输、水路运输一起，构成联合运输的优化问题。
2.综合运输网络优化模型
综合运输虽然理论上从起点到终点中途可以多次变换运输方式，但在实际中，这样处理不但会大大加大运输成本，降低经济效益，而且考虑到物理设施建设的有限性，实际运作也不具有可行性，因此，根据当前运输领域运作实际，我们假定直接连接起点和终点都是公路运输方式，后续可根据需要变换方式和路径，并且整个物流过程中，变换运输方式最多2次，否则视为不合理路径。根据上述描述，可构建联合运输网络图如图1所示。但需要注意的是，终点位置并不是唯一的，终点位置会直接影响到配送总费用，终点位置的确定也就是设施选址问题。配送过程从图1终点出发，配送到附近的多个网点，完成整个物流过程。
2.1 综合运输优化模型
图3构建了一个无向图G=（V，E），V表示网络中的所有物流中转或起止节点；E表示边集，包括不同方式的运输线路和运输方式之间的转换连接。起点出发都统一用公路运输。模型假设在两个节点之间货物不可分割，即2个节点间只能选择一种运输方式，每个节点有资格和能力进行转变运输方式的操作，会花费时间和经济成本，但不考虑仓储费用。
联合运输环节建立模型如下：
目标函数由运输费用、变换运输方式费用（简称换装费用）构成。式（1）中表示从节点i到i+1之间，运输方式为k时的运输费用；，1表示选择该k种运输方式，0表示不选k种运输方式；表示在节点i由k到l的换装费用，，1表示节点i选择由k到l，0表示节点i不选择由k到l。式（2）表示2个节点之间只能选择一种运输方式，式（3）表示在某一个节点处，至多发生一次转换，式（4）表示如果在节点i运输方式由k转换为l，则从节点i-1到城市i，运输方式为k，从节点i到节点i+1，运输方式采用l。
2.2 车辆路径问题
车辆路径问题是指在客户需求位置已知的情况下，确定车辆在各个客户间的行程路线，使得运输路线最短或运输成本最低。配送中心配送的车辆调度及路线安排问题可描述为：在配送中心位置、客户点位置和道路等已知的情况下，对m辆车，n个客户点，确定车辆分配（每辆车负责的客户点）及每辆车的行车路线，使成本最小。
其中J为服务网点的集合，K为配送车辆的集合，QK是车辆的最大容量，Cij是从i到j的配送费用，dj网点j的需求量，Ujk是顾客被访问的顺序号，N是网点总数量，，若车辆k从顾客i行驶到j则为1，否则为0。式（6）为目标函数，以总的配送费用最小为目的。式（7）为每个顾客只能被服务一次的约束条件。式（8）为防止同一个地点之间巡回的约束条件。式（9）是车辆容量限制约束条件。式（10）是保证巡回路为封闭回路的约束条件，即车辆从物流中心出发，最后一定要再回到物流中心。 3.双层规划模型
双层规划模型是多层规划的特例，由上层模型（U）和下层模型（L）组成。上层决策者通过设置的值影响下层决策者，因此限制了下层决策者的可行约束集，上层决策者通过下层决策者的目标函数与下层决策者相互作用。下层决策变量y是上层决策变量的函数，即y=y（x），这个函数被称为反应函数。
在本文中，上层决策部门可以通过策略改变运输方式、运输路径和运输终点位置（即配送中心），从而影响下层客户对配送中心的选择，但不能控制他们的选择。客户从自身费用最小的角度出发，选择合适的配送中心为其服务。这种关系可以用双层规划模型进行描述，上层规划可以描述为物流企业确定最佳的运输方式、配送中心位置及配送方案，使得总成本最小（包括运输成本、换装成本和配送成本）。而下层规划则描述了在多个配送中心存在的条件下，客户可选择不同配送中心提供服务，目标是使客户的花费最低。
上层规划表示为：
（12）
上层模型优化运输、换装和配送的总费用，公式（2）-（4）、（7）-（11）作为约束条件。下层模型从客户角度考虑，在现实中，客户寻求提供配送服务的对象，受到其他客户的影响。当许多客户都被同一个配送中心提供服务时，自然费用会增加，于是有些客户会选择其他配送中心，反之亦然。这一现象可用需求函数描述：
（13）
为第i个客户要求第j个配送中心提供服务的最小费用。一般讲，所有客户的需求函数具有基本一致的形式。这样下层规划可描述为：
（14）
（15）
式中为需求函数的反函数，可用幂函数表示。Sj为配送中心j的供应能力；M为一任意大的正数。下层规划表示客户选择最优的配送中心，式（15）保证每个用户的需求都能得到满足。
4.求解算法
双层规划问题的求解，是NP-hard问题，求解一般都相对繁琐，本文采用遗传算法求解。遗传算法借鉴生物进化遗传思想，通过选择、交叉、变异等操作，不断进行群体进化求得优化解。遗传算法的具体过程如下：
Step 1：设定遗传计算的相关参数，包括编码方案、变异率、交叉率、群体规模和进化代数，建立初始群，设定当前进化代数；
Step 2：对群体中的每个个体，作为上层规划的临时解，代入下层模型，求解公式（14）的最优解；
Step 3：对计算得出的下层最优解，反推到上层模型，获得上层规划本次计算的最终解；
Step 4：若到达进化代数要求或有当前最优解满足预定义的偏差要求，则结束，否则继续；
Step 5：利用轮盘赌思想，执行复制操作，注意每次保留最优的前5个个体；
Step 6：执行交叉操作，根据当前建立的逻辑规则，保留或丢弃交叉结果；
Step 7：根据变异率执行变异操作；
Step 8：返回Step2。
5.实例验证
为验证本文建立的模型的有效性，我们利用一模拟实例进行计算分析。假定干线运输网络如图2所示，主要有公路、铁路、水运三种运输方式，在A、B、C节点处可以换装，图中数字表示距离，以Km为单位。干线运输中公路、铁路、水路每车（船）载重量分别为20、500、1000吨，配送汽车载重量为1.5吨，公路、铁路、水路的平均运输费用为1、0.3、0.1元/（吨·公里），配送费用为0.5元/（Kg·公里）。表1给出了17个配送节点中一部分节点的参数，包括节点坐标和节点的配送需求量。其中编号为1、2、3、9、15的五个节点为干线运输的终端节点，从中选择几个节点作为配送中心。假定C1、C2、C3至这五个节点的距离相同，即费用相同。
根据遗传算法，本文利用MATLAB工具编写了程序求解该实例问题。求解过程中根据效果多次调整相应经验参数，确定了最终取值：群体规模M=50，进化代数P=50000，交叉率=0.45，变异率=0.1。同时利用LINGO软件利用分支定界方法求解该问题，获得全局最优解。
通过多次寻优验证，对上述问题求得最优解，确定终点两个，编号为2、3的节点作为配送中心，干线运输线路为：起点—A3—B3—B1—C1—节点2，起点—A3—B3—B1—C1—节点3。以节点2、3为配送中心的配送方案如图3所示。该方案比全局最优解的费用高出2.4%，作为准优解完全可以接受，但花费的时间比分支定界方法节省了82.7%，证明该方案是高效的。
6.结语
本文考虑了综合运输网络中多种运输方式联合优化，并与车辆路径问题相结合，两者统一在双层规划模型中，上层规划优化物流总成本，下层规划考虑客户配送成本最小化。本文采用遗传算法求解该双层规划模型，并与分支定界方法相比较，结果证明该方法可高效求得准优解。
参考文献
[1]孙少龙，吴小涛，等.PSO算法在物流配送车辆路径优化模型中的应用[J].电子世界，2012（8）：77-79.
[2]刘舰，俞建宁.多式联运运输方式选择的模型和算法[J].兰州交通大学学报，2010，29（1）：56-61.
[3]孙华灿，李旭宏，等.综合运输网络中合理路径优化模型[J].东南大学学报，2008，38（5）：873-877.
[4]张维泽，林剑波，等.基于改进蚁群算法的物流配送路径优化[J].浙江大学学报，2008，42，4：574-578.
基金项目：交通运输部科技项目“综合物流运输配送网络优化技术的研究”（2011319817490）；山东省“蓝黄”两区课题“做大做强海洋交通运输物流业对策研究”（2012-L-53）。
作者简介：
陈德留（1989—），男，山东济宁人，山东交通学院硕士研究生，主要研究方向：物流工程，物流优化技术。
张良智（1977—），男，山东寿光人，硕士，山东交通学院副教授，主要研究方向：智能算法，优化技术。
【关键词】综合运输；网络优化；车辆路径问题；双层规划；遗传算法
随着物流行业的不断飞速发展，多种运输方式被集成在一起共同发挥作用，综合运输体系不断完善，多式联合运输已经成为我国乃至国际物流及运输业发展的趋势。在整个物流环节中，从货品出发的源头开始，干线运输方式的选择、运输线路的优化以及末端配送的方案都是联合运输中的主要内容。在干线运输环节，公路、铁路、水运等运输方式都已发挥了重要作用，综合交通体系在国内和国际多个层次已经逐渐形成。
在干线运输环节的优化问题，包括两个方面，运输方式的选择和运输路径的优化，而两个问题又是相互影响的，因此本文合并为多种运输方式的联合运输优化问题。在这一方面已经有所研究。已有的文献大多是以运输时间长度、运输成本费用或者服务水平中的一个或多个作为研究目标进行最小化求解，建立联合运输路径的选择与优化的模型。魏际刚等对多式联运中系统协调问题进行了研究，提出了布局、结构、信息等5个方面的问题。刘舰等建立了基于综合运输成本最小和运输风险最小的多目标综合优化模型，孙华灿等建立了一个含路径合理性约束的联合运输路径优化模型。
在配送环节，一般定义为车辆问题（Vehicle Routing Problem，简称VRP）。蒋忠中等并采用模糊数表示车辆行驶时间和顾客服务时间的不确定性，建立了VRP的模糊规划模型；贺国先在满足车辆满载约束的同时充分考虑货物的运到期限，继而建立配送方案模型。求解配送路径优化问题的方法很多，常用的有旅行商法、动态规划法、节约法、扫描法以及蚁群算法、遗传算法和禁忌搜索等人工智能方法。
作为一个整体的物流过程，运输和配送都是不可缺少的，而且两者之间也是相互影响和作用的，上述文献中大多数只考虑了其中某个环节，问题设定有一定的缺陷性。基于此本文将干线运输的综合运输方式优化选择和车辆路径问题综合考虑，建立一个统一的模型研究该问题，将运输费用、中转费用、运输时间、配送费用等作为总成本联合优化。同时考虑到问题的复杂性，本文引入双层规划问题求解该模型，在优化物流成本的同时也充分考虑了用户配送选择问题。
1.综合运输问题
物流过程中综合运输方式完成一次运输任务的过程中，可包括任何两种方式之间的转换，即公-铁、公-水、水-铁、水-公、铁-水、铁-公。由于不同运输方式之间相对独立，运输方式的转换仅发生在枢纽点，不是任意位置。
一般来讲，物流过程都是以公路运输开始，以公路运输结束。但根据物流业务的不同，两头的公路运输过程可能有所差异，可能是直送，也可能是配送。为不失一般性，本文假定开头的一段公路运输过程，是直送，结尾的一段公路运输，是配送过程。配送过程的优化，就是VRP问题，直送过程，会涉及到运输方式和路径的选择，同中间环节的铁路运输、水路运输一起，构成联合运输的优化问题。
2.综合运输网络优化模型
综合运输虽然理论上从起点到终点中途可以多次变换运输方式，但在实际中，这样处理不但会大大加大运输成本，降低经济效益，而且考虑到物理设施建设的有限性，实际运作也不具有可行性，因此，根据当前运输领域运作实际，我们假定直接连接起点和终点都是公路运输方式，后续可根据需要变换方式和路径，并且整个物流过程中，变换运输方式最多2次，否则视为不合理路径。根据上述描述，可构建联合运输网络图如图1所示。但需要注意的是，终点位置并不是唯一的，终点位置会直接影响到配送总费用，终点位置的确定也就是设施选址问题。配送过程从图1终点出发，配送到附近的多个网点，完成整个物流过程。
2.1 综合运输优化模型
图3构建了一个无向图G=（V，E），V表示网络中的所有物流中转或起止节点；E表示边集，包括不同方式的运输线路和运输方式之间的转换连接。起点出发都统一用公路运输。模型假设在两个节点之间货物不可分割，即2个节点间只能选择一种运输方式，每个节点有资格和能力进行转变运输方式的操作，会花费时间和经济成本，但不考虑仓储费用。
联合运输环节建立模型如下：
目标函数由运输费用、变换运输方式费用（简称换装费用）构成。式（1）中表示从节点i到i+1之间，运输方式为k时的运输费用；，1表示选择该k种运输方式，0表示不选k种运输方式；表示在节点i由k到l的换装费用，，1表示节点i选择由k到l，0表示节点i不选择由k到l。式（2）表示2个节点之间只能选择一种运输方式，式（3）表示在某一个节点处，至多发生一次转换，式（4）表示如果在节点i运输方式由k转换为l，则从节点i-1到城市i，运输方式为k，从节点i到节点i+1，运输方式采用l。
2.2 车辆路径问题
车辆路径问题是指在客户需求位置已知的情况下，确定车辆在各个客户间的行程路线，使得运输路线最短或运输成本最低。配送中心配送的车辆调度及路线安排问题可描述为：在配送中心位置、客户点位置和道路等已知的情况下，对m辆车，n个客户点，确定车辆分配（每辆车负责的客户点）及每辆车的行车路线，使成本最小。
其中J为服务网点的集合，K为配送车辆的集合，QK是车辆的最大容量，Cij是从i到j的配送费用，dj网点j的需求量，Ujk是顾客被访问的顺序号，N是网点总数量，，若车辆k从顾客i行驶到j则为1，否则为0。式（6）为目标函数，以总的配送费用最小为目的。式（7）为每个顾客只能被服务一次的约束条件。式（8）为防止同一个地点之间巡回的约束条件。式（9）是车辆容量限制约束条件。式（10）是保证巡回路为封闭回路的约束条件，即车辆从物流中心出发，最后一定要再回到物流中心。 3.双层规划模型
双层规划模型是多层规划的特例，由上层模型（U）和下层模型（L）组成。上层决策者通过设置的值影响下层决策者，因此限制了下层决策者的可行约束集，上层决策者通过下层决策者的目标函数与下层决策者相互作用。下层决策变量y是上层决策变量的函数，即y=y（x），这个函数被称为反应函数。
在本文中，上层决策部门可以通过策略改变运输方式、运输路径和运输终点位置（即配送中心），从而影响下层客户对配送中心的选择，但不能控制他们的选择。客户从自身费用最小的角度出发，选择合适的配送中心为其服务。这种关系可以用双层规划模型进行描述，上层规划可以描述为物流企业确定最佳的运输方式、配送中心位置及配送方案，使得总成本最小（包括运输成本、换装成本和配送成本）。而下层规划则描述了在多个配送中心存在的条件下，客户可选择不同配送中心提供服务，目标是使客户的花费最低。
上层规划表示为：
（12）
上层模型优化运输、换装和配送的总费用，公式（2）-（4）、（7）-（11）作为约束条件。下层模型从客户角度考虑，在现实中，客户寻求提供配送服务的对象，受到其他客户的影响。当许多客户都被同一个配送中心提供服务时，自然费用会增加，于是有些客户会选择其他配送中心，反之亦然。这一现象可用需求函数描述：
（13）
为第i个客户要求第j个配送中心提供服务的最小费用。一般讲，所有客户的需求函数具有基本一致的形式。这样下层规划可描述为：
（14）
（15）
式中为需求函数的反函数，可用幂函数表示。Sj为配送中心j的供应能力；M为一任意大的正数。下层规划表示客户选择最优的配送中心，式（15）保证每个用户的需求都能得到满足。
4.求解算法
双层规划问题的求解，是NP-hard问题，求解一般都相对繁琐，本文采用遗传算法求解。遗传算法借鉴生物进化遗传思想，通过选择、交叉、变异等操作，不断进行群体进化求得优化解。遗传算法的具体过程如下：
Step 1：设定遗传计算的相关参数，包括编码方案、变异率、交叉率、群体规模和进化代数，建立初始群，设定当前进化代数；
Step 2：对群体中的每个个体，作为上层规划的临时解，代入下层模型，求解公式（14）的最优解；
Step 3：对计算得出的下层最优解，反推到上层模型，获得上层规划本次计算的最终解；
Step 4：若到达进化代数要求或有当前最优解满足预定义的偏差要求，则结束，否则继续；
Step 5：利用轮盘赌思想，执行复制操作，注意每次保留最优的前5个个体；
Step 6：执行交叉操作，根据当前建立的逻辑规则，保留或丢弃交叉结果；
Step 7：根据变异率执行变异操作；
Step 8：返回Step2。
5.实例验证
为验证本文建立的模型的有效性，我们利用一模拟实例进行计算分析。假定干线运输网络如图2所示，主要有公路、铁路、水运三种运输方式，在A、B、C节点处可以换装，图中数字表示距离，以Km为单位。干线运输中公路、铁路、水路每车（船）载重量分别为20、500、1000吨，配送汽车载重量为1.5吨，公路、铁路、水路的平均运输费用为1、0.3、0.1元/（吨·公里），配送费用为0.5元/（Kg·公里）。表1给出了17个配送节点中一部分节点的参数，包括节点坐标和节点的配送需求量。其中编号为1、2、3、9、15的五个节点为干线运输的终端节点，从中选择几个节点作为配送中心。假定C1、C2、C3至这五个节点的距离相同，即费用相同。
根据遗传算法，本文利用MATLAB工具编写了程序求解该实例问题。求解过程中根据效果多次调整相应经验参数，确定了最终取值：群体规模M=50，进化代数P=50000，交叉率=0.45，变异率=0.1。同时利用LINGO软件利用分支定界方法求解该问题，获得全局最优解。
通过多次寻优验证，对上述问题求得最优解，确定终点两个，编号为2、3的节点作为配送中心，干线运输线路为：起点—A3—B3—B1—C1—节点2，起点—A3—B3—B1—C1—节点3。以节点2、3为配送中心的配送方案如图3所示。该方案比全局最优解的费用高出2.4%，作为准优解完全可以接受，但花费的时间比分支定界方法节省了82.7%，证明该方案是高效的。
6.结语
本文考虑了综合运输网络中多种运输方式联合优化，并与车辆路径问题相结合，两者统一在双层规划模型中，上层规划优化物流总成本，下层规划考虑客户配送成本最小化。本文采用遗传算法求解该双层规划模型，并与分支定界方法相比较，结果证明该方法可高效求得准优解。
参考文献
[1]孙少龙，吴小涛，等.PSO算法在物流配送车辆路径优化模型中的应用[J].电子世界，2012（8）：77-79.
[2]刘舰，俞建宁.多式联运运输方式选择的模型和算法[J].兰州交通大学学报，2010，29（1）：56-61.
[3]孙华灿，李旭宏，等.综合运输网络中合理路径优化模型[J].东南大学学报，2008，38（5）：873-877.
[4]张维泽，林剑波，等.基于改进蚁群算法的物流配送路径优化[J].浙江大学学报，2008，42，4：574-578.
基金项目：交通运输部科技项目“综合物流运输配送网络优化技术的研究”（2011319817490）；山东省“蓝黄”两区课题“做大做强海洋交通运输物流业对策研究”（2012-L-53）。
作者简介：
陈德留（1989—），男，山东济宁人，山东交通学院硕士研究生，主要研究方向：物流工程，物流优化技术。
张良智（1977—），男，山东寿光人，硕士，山东交通学院副教授，主要研究方向：智能算法，优化技术。