【www.zhangdahai.com--交通运管公文】
摘 要：为满足电子行业独特的物流配送需求，依据电子行业的特点，研究一种变形的车辆调度问题（VehicleRouteingProblem，VRP）.将产品的配送与安装的同步性进行分离，建立以最小配送和安装旅行时间为目标的混合整数非线性规划（Mixed�IntegerNonlinearProgramming，MINP）模型，即基于软时间窗的配送和安装车辆调度优化模型.对算例计算结果的比较分析表明采用分层方法和遗传算法（GeneticAlgorithm，GA）的可行性和有效性.该模型可以提高电子行业的物流配送效率，降低物流成本，提高服务水平.
关键词：车辆调度；时间窗；问题分解；层次方法；遗传算法
中图分类号：F252.14；O221.2；TP183 文献标志码：A
Optimizationforvehiclerouteingwithseparateddeliveryand installationofproductsbasedonsofttimewindows
PANGHaijun，DINGYizhong
（AcademyofScience＆Technology，ShanghaiMaritimeUniv.，Shanghai201306，China）
Abstract：Inordertosatisfytheuniqueneedoflogisticsinelectronicsindustry，avariantoftheVehicle RouteingProblem（VRP）isstudiedbasedontheuniquecharacteristicsofelectronicsindustry.Thesyn�chronismofthedeliveryandinstallationofproductsisseparated，andaMixed�IntegerNonlinearProgram�ming（MINP）modelispresentedtominimizethetravelingtimeofdeliveryandinstallation，whichisthe optimizationmodelofVRPfordeliveryandinstallationbasedonsofttimewindows.Comparativeanalysis oftheresultsillustratesthefeasibilityandeffectivenessofthehierarchicalapproachandGeneticAlgo�rithm（GA）.Themethodcanimprovetheefficiencyoflogisticsdistribution，reducetheenterprises’lo�gisticscost，andimprovetheservicelevel.
Keywords：vehiclerouteing；timewindow；problemdecomposition；hierarchicalapproach；genetical�gorithm
0 引 言
近些年，电子行业在售后服务方面发生巨大的变化，许多新兴产品不仅需要配送，而且需要专业的安装.它们包括挂壁式电视机（家庭影院系统）、洗衣机和干衣机、带有净水系统的冰箱、特殊烹调台面、数控机、电脑服务器等.然而，由于维持全国配送和客户服务网络的费用太高，企业采取将配送业务外包给第三方物流企业的方法，仅保留自己的服务队伍.于是，电子行业中出现产品配送与安装相分离的现象.依据这一特点，本文研究一种变形的车辆调度问题（VehicleRouteingProblem，VRP），以满足其独特的物流配送需求.
KIM等［1］首先对此种变形的VRP进行研究.他假设安装车辆必须在配送车辆访问（或者到达）那个顾客之后，在服务水平之内访问顾客，从而保证这两种类型的车辆同步，以满足顾客配送和安装的服务质量.在他们的研究中，可以将服务水平看作是硬时间窗［2］VRP的变形.当前，对此种变形的VRP的研究都是在硬时间窗的约束条件下对模型进行的研究，然而在实际物流配送中其复杂程度远超过于此.本文在前人研究的基础上考虑在软时间窗［3］约束下的VRP，因为软时间窗与实际情况更接近.此约束条件既可满足顾客的服务质量，同时又可兼顾企业的利润最大化.
可以将此变形的VRP看作是两个传统VRP的组合：一个是配送车辆的VRP，它具有容量限制的VRP（CapacityVRP，CVRP）的特点［4�5］；另一个是安装车辆的VRP，它具有带时间窗VRP的特点［6�7］.由于该模型的复杂程度远远超过经典VRP模型的复杂程度，即使采用启发式算法编程求解也很复杂，KIM等［1］引入层次的概念将原问题划分为若干子问题的组合，从而降低问题的规模.分层后的模型是早被国际证实的NP难问题，采用正常方法求解十分困难，因此可利用遗传算法（GeneticAlgorithm，GA）在一个合理时间内有效解决所考虑的问题.
继续采用层次的概念将原问题变为两个子问题的组合，即：第一阶段是配送车辆的VRP，确定配送车辆的路线和调度；第二阶段是安装车辆带软时间窗的VRP（VRPwithSoftTimeWindow，VRPSTW），基于第一阶段的计算结果，获得第二阶段安装车辆的路线和调度.对大量不同规模例子的的计算表明：文中所采用的分层GA的可行性和有效性；第一阶段的最好结果并不一定是原问题的最佳结果.该研究还可以对制订配送车辆和安装车辆调度的有效管理计划提供帮助.
1 基于软时间窗的配送和安装车辆调度优化模型
1.1 问题描述与假设
给定一配送中心和多个不同的需求点，已知配送中心拥有两种类型的最大车辆数，以及每个需求点（客户）的位置，需求数量（不超过货车最大载重量）及是否需要安装.对于只需要配送的顾客点，只允许一辆配送车辆访问一次；对于需要配送和安装的顾客，只允许一辆配送车辆和一辆安装车辆分别访问一次.所有车辆开始从同一配送中心出发对顾客进行服务，安装车辆可以在配送车辆之前访问顾客，这就在对应的顾客位置产生安装车辆的等待时间，超过规定时间就要受到一个与时间成正比的惩罚.如果安装车辆在配送车辆之后访问客户，若不能在顾客可以忍耐的时间内到达，就要受到一个与时间成正比的惩罚.车辆完成服务后返回配送中心，所有客户的需求都必须满足.求：如何安排配送车辆和安装车辆的路线，使整个服务过程总时间最少，总时间包括固定安装时间、等待时间及惩罚时间、行驶时间.图1显示服务水平为软时间窗的VRP的例子.
对上述问题描述，假设以下几点成立：
（1）不允许车辆超载；
（2）配送中心有足够供调度的车辆，且每辆车有最大的运行时间；
（3）所有车辆单位时间内行驶的路程相同，且各客户点与配送中心以直线连接；
在VRPSTW数学模型中，将运行距离或运输费用统一转换成运行时间在模型中体现，目标函数是所有配送车辆和安装车辆的总运行时间最小.式（2）和（12）限制从配送中心出发的车辆；约束（3），（4），（5），（13），（14），（15）分别保证车辆都由配送中心出发并最终回到配送中心；约束（6），（7），（16），（17）表示每个客户只能受到一辆车服务并且每个客户都得到服务；约束（8）表示每辆车所运送的货物重量不能超过车辆载重的限制；约束（9）和（18）表示防止车辆在内部出现子循环；约束（10）和（19）表示车辆在客户点不动时为零；（11）和（20）为变量取值约束；式（21）表示车辆从配送中心出发和安装时间为零；约束（22）表示配送车辆p到达顾客点i的时间加上i到j的行驶时间，小于等于车辆到
1.4 算法设计
由于VRP是世界公认的NP难问题，本文所研究的变形VRP更是在经典VRP上的叠加，困难度远超经典VRP.若采用直接的方法求解，很少的客户点求解规模也很大，即使采用启发式算法编程求解也非常复杂.为了获得原始问题的良好解决方案，本文在文献［1］的基础上继续引入分层思想将原问题分为两个阶段，每阶段包括一个子问题.第一阶段的子问题是一个配送车辆的VRP，解决配送车辆的路径和时间安排；第二阶段的子问题是一个安装车辆的VRPSTW问题.第一阶段子问题是原问题的部分解决方案，同时也用作第二阶段的子问题数据输入部分.依据第一阶段子问题提出的部分解决方案，确定第二阶段子问题中安装车辆的路径和时间安排方案.安装车辆的路径和时间安排也是原问题的部分解决方案.解决第二阶段的子问题后，两种类型车辆的协同问题也就得到解决.最后，两个子问题的部分解决方案也就是原来问题的解决方案.
通过分层方法将原问题划分为两个阶段的子问题，从而简化原问题的规模和复杂度.对于规模不太大的问题，可以通过LINGO求得目标函数的精确解.但LINGO不适用于大规模的问题，本文通过GA求解，只能得到近似解.通过利用LINGO9.0和GA分别求得精确解和近似解，并对两种结果进行比较分析.
此外，为了进一步验证采用分层的GA的有效性和可行性，将算例中的客户点增加至30个，其中需要安装的客户点为10个，每个顾客的需求量是1～4个，6辆配送车辆和2辆安装车辆.求解过程中总的运算时间为125s，运算结果为843.4min，运行路径见图4（配送中心出发到客户点和返回配送中
2.3 求解方法有效性分析
为了说明采用分层的GA的有效性，首先用LINGO9.0求解出该算例以最小运行时间为目标函数的车辆行驶路径结果；再用分层的方法将模型分为两个子问题考虑；最后通过GA求解近似结果.从图3中可以看出，虽然近似解结果不如精确结果优异，但是可以说明采用分层的GA所求结果的可行性.由于LINGO9.0只能求解较小规模的MINP模型，且费时较长，在现实生活中物流配送量往往很大，要求在合理的时间得到配送方案，精确算法就不适合，而GA可以在一个合理的时间内得到一个较满意的解.为了进一步对所提出的分层的GA的有效性和可行性检验，文中随机生成大量规模较大的MINP模型进行求解计算，图4就是其中一个算例.计算结果表明：该分层算法可以在合理的时间内找到问题的最优解或者近似最优解；第二阶段子问题的结果受第一阶段子问题结果的影响，第一阶段子问题的最优解决方案不能保证原问题的解决方案最优.
3 结束语
随着现代物流配送的发展，不同行业对其要求不同，各有特点.本文依据电子行业配送的新特点，研究一种变形的VRP.所考虑的问题是两种不同类型的配送服务：一种只需要配送服务，一种是配送与安装都需要的服务.为了高效率地满足顾客需求，企业采用两种类型配送车辆分开运作的方式.在保证顾客的服务质量方面，所要考虑的问题是如何更好地解决两种车辆的协同操作.本文在对所提出的模型求解时采用分层的方法进行求解，这将导致第二阶段子问题的最优结果受第一阶段子问题最优结果的影响，第一阶段子问题的最优解决方案不能保证是原问题的最优解决方案.未来的研究可以同时考虑两个子问题，在此模型的基础上研究不确定因素下的模型等.
参考文献：
［1］KIMKyoungCheol，LEEShiwoo.Hierarchicalapproachtovehiclerouteingproblemfordeliveryandinstallation［J］.SciDirect，2010：7458�7471.
［2］vanLANDEGHEMHRG.Abi�criteriaheuristicforthevehiclerouteingproblemwithtimewindows［J］.EurJOperationalRes，1988，36（2）：217�226.
［3］KOSKOSIDISYA，POWELLWB，SOLOMONMM.Anoptimization�basedheuristicforvehiclerouteingandschedulingwithsofttimewindow constraints［J］.TransportingSci，1992，26（2）：69�85.
［4］CAMPOSV，MOTAE.Heuristicproceduresforthecapacitatedvehiclerouteingproblem［J］.ComputationalOptimization＆Application，2000，16（3）：265�277.
［5］PISINGERD，ROPKES.Ageneralheuristicforvehiclerouteingproblems［J］.ComputOperationRes，2007，34（8）：2403�2435.
［6］ALVARENGAGB，MATEUSGR，deTOMIG.Ageneticandsetpartitioningtwo�phaseapproachforthevehiclerouteingproblemwithtimewin�dows［J］.SciDirect，2007，34（6）：1561�1584.
［7］CHENGChibin，WANGKengpin.Solvingavehiclerouteingproblemwithtimewindowsbyadecompositiontechniqueandageneticalgorithm［J］. SciDirect，2009，36（4）：7758�7763.
［8］TANKC，LEELH，OUK.Artificialintelligenceheuristicsinsolvingvehiclerouteingproblemswithtimewindowconstraints［J］.EngApplica�tionsofArtificialIntelligence，2001，14（6）：825�837.
［9］BERGERJ，BARKAOUIM，BRASYO.Aroute�directedhybridGAapproachfortheVRPTW［J］.InformSystems＆OperationalRes，2003，41（2）：179�194.
［10］盛丽俊，周溪召.带有时间窗的车辆路径问题优化［J］.上海海事大学学报，2007，28（4）：64�67.
［11］李军，谢秉磊，郭耀煌.非满载车辆调度遗传算法［J］.系统工程理论与实践，2000，20（3）：235�239.
（编辑 廖粤新）
