【关键词】综合运输；网络优化；车辆路径问题；双层规划；遗传算法
随着物流行业的不断飞速发展，多种运输方式被集成在一起共同发挥作用，综合运输体系不断完善，多式联合运输已经成为我国乃至国际物流及运输业发展的趋势。在整个物流环节中，从货品出发的源头开始，干线运输方式的选择、运输线路的优化以及末端配送的方案都是联合运输中的主要内容。在干线运输环节，公路、铁路、水运等运输方式都已发挥了重要作用，综合交通体系在国内和国际多个层次已经逐渐形成。
在干线运输环节的优化问题，包括两个方面，运输方式的选择和运输路径的优化，而两个问题又是相互影响的，因此本文合并为多种运输方式的联合运输优化问题。在这一方面已经有所研究。已有的文献大多是以运输时间长度、运输成本费用或者服务水平中的一个或多个作为研究目标进行最小化求解，建立联合运输路径的选择与优化的模型。魏际刚等对多式联运中系统协调问题进行了研究，提出了布局、结构、信息等5个方面的问题。刘舰等建立了基于综合运输成本最小和运输风险最小的多目标综合优化模型，孙华灿等建立了一个含路径合理性约束的联合运输路径优化模型。
在配送环节，一般定义为车辆问题（VehicleRoutingProblem，简称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问题，求解一般都相对繁琐，本文采用遗传算法求解。遗传算法借鉴生物进化遗传思想，通过选择、交叉、变异等操作，不断进行群体进化求得优化解。遗传算法的具体过程如下：
Step1：设定遗传计算的相关参数，包括编码方案、变异率、交叉率、群体规模和进化代数，建立初始群，设定当前进化代数；
Step2：对群体中的每个个体，作为上层规划的临时解，代入下层模型，求解公式（14）的最优解；
Step3：对计算得出的下层最优解，反推到上层模型，获得上层规划本次计算的最终解；
Step4：若到达进化代数要求或有当前最优解满足预定义的偏差要求，则结束，否则继续；
Step5：利用赌思想，执行复制操作，注意每次保留最优的前5个个体；
Step6：执行交叉操作，根据当前建立的逻辑规则，保留或丢弃交叉结果；
Step7：根据变异率执行变异操作；
Step8：返回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）。
作者简介：
关键词:3G;GIS;区域多配送;优化调度
中图分类号:TP335文献标识码:A文章编号:1007-9599(2010)05-0000-02
ApplicationofModernCommercialandDistributionBasedon3GGeographicInformationSystem
XuQianqian
(TaizhouVocational&TechnicalCollege,Taizhou318000,China)
Abstracts:Geographicinformationsystem(GIS)technologyinrecentyearsofrapidgrowthoftheinformationanalysisofspacetechnology.
Deploymentproblem(vehicleschedulingproblem,vsp)'slogisticsdevelopmentofanimportantarea.Theapplicationbasedon3Gtechnologyisansoftwareapplicationofmodernmanagementscheduling,dispatchofthetheoryandscheduling,usingthesoftwareandinformationtechnologytoeffectivelymanagethedistributionandlogisticssystem.TheauthorinZhejiangwithalargebusinessbackground,integratedlogisticssystemsengineeringpracticediscussionisbasedongeographicalinformationsystemstechnologies3Gtheareaoflogisticsdistributioncentrefortheestablishmentofamathematicalmodelanddesignandoptimizethealgorithmtotherelevantissues.
Keywords:3G;GIS;Areadeliveries;Attempteroptimization
一、引言
地理信息系统技术是近些年迅速发展起来的一门空间信息分析技术,在资源与环境应用领域中,它发挥着技术先导的作用。GIS技术不仅可以有效地管理具有空间属性的各种资源环境信息,对资源环境管理和实践模式进行快速和重复的分析测试,便于制定决策、进行科学和政策的标准评价,而且可以有效地对多时期的资源环境状况及生产活动变化进行动态监测和分析比较,也可将数据收集、空间分析和决策过程综合为一个共同的信息流,明显地提高工作效率和经济效益,为解决资源环境问题及保障可持续发展提供技术支持。
支付系统、配送系统和安全系统是影响电子商务发展的三大因素,物流配送已成为制约电子商务发展的一个瓶颈。基于软件GIS技术项目化就是应用现代管理调度思想、调度理论和调度方法,利用软件信息技术,有效地管理物流配送,实现物流系统的整体优化。车辆调度问题是物流研究中的一个重要领域。对于减少企业物流配送成本有着具有很重要的意义。作者以浙江某大型连锁企业物流系统为背景,结合工程实践讨论基于3G技术的区域多配送中心物流调度的数学模型建立及其算法设计、优化等有关问题。
二、GIS简介
地理信息系统脱胎于地图,它们都是地理信息的载体,具有获得、存储、编辑、处理、分析与显示地理数据的功能。一个完整的GIS主要由四个部分构成,即计算机硬件系统、计算机软件系统、地理数据和系统管理操作人员。其核心部分是计算机系统,空间数据反映GIS的地理内容,而管理人员和用户则决定系统的工作方式和信息表示方式。GIS发展的另一个重要趋势是从软件向服务的转变。尤其是2001年以来网格计算概念的爆发,在学术界和信息技术领域掀起了一股网格的热潮。GIS作为一个与生俱来的分布式系统,在标准和互操作方面一直没有停止过努力。
三、问题描述
VSP问题基本上可分为无时间窗口约束的vsp和带有时间窗口约束的vsp。主要讨论带有时间窗口的车辆调度模型,问题描述为:从多个物流中心用多台配送车辆向多个客户送货,每个配送中心的位置一定,每个客户的卸货位置和货物需求量一定,每台配送车辆的车载重量一定,要求将货物送到的时间窗口一定,配送中心要满足所有客户的需求,要求合理安排车辆配送路线和车辆行车时间,使目标函数得到优化。带有时间窗口约束的vsp要求每项配送任务必须在要求的时间范围内完成,若超出这个范围,则给以一定的惩罚。车辆在要求时间之前到达客户卸货位置,则车辆在此等待,产生了机会成本损失;若车辆在指定的时间之后到达客户卸货位置,则服务被延迟,需要支付一定的罚金。
四、数学模型建立思路
从配送成本上考虑,在规模大的城市内单一配送中心的成本较高,为了适应这种状况,多数大型物流公司在同一个大城市内一般会设立多个配送中心。对于多个配送中心车辆调度的问题,首先,把需要配送的客户划为不同的区域,每个区域只有一个配送中心,可同时由多辆车辆进行配送,然后,对每个区域进行最有线路的求解,以配送费用最小为最终目标。
五、禁忌搜索法算法设计
禁忌搜索算法是求解最优解的智能化算法,它引入了人工智能技术,仿效人类行为,并应用一些学习规则确定搜索方向,以避免解的局部循环。
算法的主要步骤如下:
第一步骤:选定一个初始解Yu;令禁忌表tabulist=Φ;
第二步骤:如果满足终止准则,则转第四步骤;否则在一定搜索方向产生移动值Move,并在Yu的领域D(Yu)中选择出满足禁忌要求的侯选解CD(Yu),转到第三步骤;
第三步骤:在CD(Yu)中选一个最好的解JieBest,使得Yu=JieBest,更新禁忌表tabulist,转到第二步骤;
第四步骤:输出计算结果,停止程序。
六、3G技术(GIS技术)在物流配送中的运用
物流配送的原则是由一个出发点到达多个分散的客户点的多点路径,出发点一般定义为配送点所在位置,也可以定义为某些个特殊的位置,例如某个发货点;多点则指所有客户的送或是经营地址,这些信息点在系统实施优化之前需要进行采集,采集到经纬度信息构成了整个系统的基础数据。
GIS运算的前提,仍然是将配送区域进行划分,根据地理环境可划分为6个区域,每个区域五个工作日,每日一个区域内纳入GIS运算的客户基本在400~800个之间。这800多个信息点的确定,一方面仍然需要线路规划人员的经验判断,与以前不同的是,面对可视化的地图界面,系统提供了客户的地理位置、道路信息、近三个月的平均配送量等信息,结合以前的经验,使得第一步的划分较之从前,快捷、准确、预见性更高。
GIS软件技术线路优化具体模块:
(一)车辆调度。日常情况下,可以用系统默认的车辆排序,也可加以人工干预,由车辆调度人员安排,这对于峰值期间的配送任务合理调度分配意义尤其重要,当以后纳入GIS的配送区域不断扩大,这种调度的意义就超越了简单的任务分配,达到一个对全局配送资源的综合利用的境界。
(二)每日线路优化。对每一辆车内的配送线路进行优化,计算出最合理的线路。由于单车涉及的计算量已经比较小,可以实时运算,在非常短的时间内完成,不必作预先处理。计算完毕,分车的数据就可以交给物流货物分拣部门按序分拣,同时通过GPRS将配送任务发送至各车的车载终端。
七、结论
本文在对区域多配送中心物流车辆配送问题进行分析的基础上,建立该问题直观描述的数学模型,并考虑了较为接近实际的约束条件,并结合模型的特点运用信息软件技术设计了禁忌搜索法算法。最终通过工程初步实践,表明了上述模型应用的可行性和有效性。
参考文献:
[1]MARCGOETSCHALCKX,GEORGEputerAidedDesignofIndustrialLogisticsSystems.IndustrialSystemsEngineeringofTechnology,1994:12-37
[2]丁立言,张铎.物流配送.清华大学出版社,2007
[关键词]电子商务配送中心GIS
随着21世纪信息化、电子化和网络化的迅速普及，电子商务得到了快速的发展。电子商务是基于浏览器/服务器的应用方式，实现客户和企业信息沟通、网上购物、电子支付的一种新型的运作方式。
电子商务的特殊性就在于信息流、商流、资金流在互联网上实现，而电子商务的物流配送是不可能在网上实现的，最多可以通过网络来优化。它是信息流和资金流的基础与载体。因此，在网上实现商流活动之后，对商品的转移提供低成本、适时、适量的转移服务则要靠物流配送系统来完成。要保证物流配送中心系统良好运行，物流配送中心的选址至关重要。本文借助地理信息系统（GIS）的强大功能，利用六边形法则建立配送中心的空间布局的优化模型并求解。
一、配送中心的空间布局优化模型的建立
1.配送中心数目的确定。按照克理斯塔勒（W.Christaller）著名的六边形法则，假设某规划区域的配送需求密度是均匀的，而且各配送中心均能满足给其分配的配送任务，则可初步确定出在现代城市交通状况下配送车辆的经济配送半径r。若是单一配送中心规划，则配送中心的经济配送范围必然是以r为半径的一个圆；若是在多配送中心规划时，如果每个供应点的市场区都是圆形的、彼此之间相切而又不重叠的话，居住在空角里的消费者将得不到供应，如图1所示；如要不露空白，则圆与圆必须重叠，如图2所示。这时，居住在重叠区内的消费者有两个可供选择的区位。按照就近原则，重叠区可平均分割为两部分，其中位于平分线上的消费者到两个相邻的供应点的距离是相等的，这条线被称作无差别线。由于重叠区被分割，圆形的市场区即被六边形的市场区所替代，见图3所示。在多配送中心规划中其经济配送范围是以为半径的圆的内接正六边形。在具体的规划过程中，只要确定了规划区域的面积S，则可通过如下公式粗略求得配送中心的数目
2.模型的建立。将克理斯塔勒中心理论应用于配送中心布局优化时，理论中配送中心的配送区域范围是由配送中心和由该配送中心负责的配送点决定。配送中心和配送点这两者的关系是以配送企业的总费用（配送中心的建造营运费以及运送费）最小或社会综合效益最大为基础建立的。
本文的优化思路是首先将配送中心合理布点问题看作是一个连续性问题，借助GIS的空间分析功能（包括数据库含有地价属性等特点）初选个配送中心，若优化出的配送中心是居民区、大型商业建筑、办公楼以及学校等不适宜的位置，则重新分配配送任务，并将此作为新增约束条件进而重新确定配送中心的位置。
基于此，本文将配送中心合理选址问题描述为：
已知:(1)n个配送点的位置；(2)各配送点的配送需求量;(3)单位配送量单位距离的配送费率。
求解:(1)配送中心的优化数目；(2)各配送中心的最优区位。
配送中心空间合理布局的目标应该是使配送中心的经营总费用最小、交通便利以及对周围环境的影响最小。其中后两者可以利用GIS的缓存区等功能在初选时加以考虑。配送中心的总费用包括两部分：固定费用（即建造成本）和可变费用（即运送成本），其中固定费用主要和配送中心的地价等因素有关，同样可以利用GIS地价分析功能确定，所以目标函数中只考虑运送费用即可，大大简化了问题的复杂性。则目标函数可表示为：（2）
其中，为配送中心i到配送点j的距离;决策变量Xij表示第i个配送中心是否向第j个配送点配送货物，如果是，Xij值为1，否则，其值为0。
约束条件：(1)保证对所有配送点配货，即（3）
(2)保证每个配送点只由一个配送中心配货，即（4）
(3)保证配送量的非负性，即（5）
二、模型求解分析
上述模型在GIS软件系统的支持下，求解起来比较方便。因为在GIS环境下，能方便地获取各配送点的坐标、各配送中心的坐标。而且计算结果也可在屏幕上显示出来。尽管在建立规划所需的GIS数据库时，可能费工费时，但是，可以采用GIS公用数据库以节约资源。如果对原有的GIS数据库进行必要的修改，增补（如增补新建配送中心、新增配送点，删除拆除的配送中心等）之后，即可开始新的规划。
由于GIS只是一个数据库管理工具，它并不能直接用于求解规划问题的配送中心空间布局优化模型。上述模型的求解，一般采用交替选址分划法。其求解步骤为:
假设第i组配送点的数目为ni，这ni个配送点由第i个配送中心提供配货的配送费用(NF)为：（6）
于是配送中心选址模型为：（7）