基于GIS的智能配送系统研究

《基于GIS的智能配送系统研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

基于GIS的智能配送系统研究摘要现代物流是企业降低生产经营成本，提高产品市场竞争力的重要途径。配送作为物流系统中的关键环节之一．其效率和经营水平在很大程度上决定着整个物流系统的成功与否。然而，现阶段配送过程的决策主要还是依赖于人工模式，这己成为制约配送企业发展的瓶颈。将GIS技术应用于物流配送是现代物流配送发展的必然趋势，配送伴随着空间位置的动态变化，是一种典型的空间现象和过程，无论是在配送业务的操作层面，还是配送过程的管理决策层面，都需要GIS作为其技术支撑。因此．加强配送决策环节的研究以及GIS在其中的应用研究，对物流配送企业实现智能化配送管理、降低配送服务成本、提高配送效率显得至关重要。本文在系统地分析现实物流配送的业务流程和存在问题的基础上，重点剖析配送调度过程，根据配送合理化的判断标准，结合现实需求，对基于GIS的物流配送调度模型及智能配送的相关技术与方法进行了有益的探讨与研究，设计并实现了智能配送的原型系统。本文的主要研究内容及取得的研究成果包括：(1)分析了物流配送以及GIS在物流配送中应用的研究进展和存在的问题，通过对配送业务流程的详细剖析．构筑了智能化配送体系。(2)针对配送的核心问题——配送调度问题进行了重点研究，为满足实际配送中的复杂需求，建立了配送业务的优化调度模型，解决车辆选择、装载货物选择、配送路线规划等问题：针对该类问题的特点，采用遗传算法和模拟退火算法结合的方式对问题进行求解。实验证明，基于优化调度模型的求解是可行和有效的。(3)针对目前GIS软件中网络分析功能不能满足实际配送业务复杂需求的问题，本文基于物流配送信息和地理数据集成，以及GIS操作功能与配送决策分析功能集成，探讨优化调度模型与GIS集成的具体过程，由此形成了直观的配送调度方式，实现了调度决策的可视化并避免了盲目决策。另外，在集成和监控子系统的支持下，详细分析了车辆在途中的调度策略。(4)在上述研究成果的基础上，以南京市某物流企业的实际配送业务、南京市基础地理数据为基础，设计和开发了物流智能配送的原型系统，验证了本研究成果是可行性的。本文的设计思路和研究方法对现代物流配送作业过程的合理实现具有一定的借鉴作用，可以有效地提高客户的服务满意度，降低企业运营成本，符合今后物流配送的发展方向。关键词：智能配送；地理信息系统；优化调度；配送决策：遗传算法：模拟退火算法 AbstractModemlogisticsi'sanimportantwayforenterprisestoreduceproductioncostsandincreasemarketcompetitiveness．Theefficiencyandoperationlevelofthedistribution，whichisoneofthecriticalnodesinthelogisticssystem，toagreatdegreedeterminesthesuccessorfailureofthelogisticssystem．However,thedecision．makingprocessofcurrentdistributionsystemprimarilyreliesonmanuaImode，whichhasbecomethebottleneckinhibitingthedevelopmentofenterprises-TheapplicationofGIStechnologytodistributionfieldisthenecessarytrendbecaused．istributionserviceaccompanyingthedynamicchangeofspacelocationisatypicalspaceeventandprocess·TheGIStechnologicalsupportisessentialtorealizationoftheinformation_basedintelligentmanagerrlentofdistributionenterprises，whetherintheoperationallevelofdistributionbusiness，orthemanagementlevelanddecision．makinglevelofdistribution．Therefore，strengtheningtheI．esearchonthedecision．makingprocessofCUll'el'ItdistributionandtheresearchonGIS’applicationinthedistributionserviceiscrucial，itcanhelpthelogisticsenterprisesachieveintelligentdistributionmanagement，reducethedistributionservicecostandimprovedistributionefficiency．Thispapersystematicallyanalyzedtheoperationflowandexistingissuesincurrentlogisticsdistribution．Inaccordancewiththecriterionofdistributionrationalizationandincombinationwiththe口racticalneeds，thispaperdiscussedandresearchedtherelatedtechnologyandmethodsaboutthedistributionschedulingmodelandintelligentdistributionsystembasedonGIS．Afterwards，itdesignedandrealizedaprototypesystemofintelligentdistribution．Theprimaryresearchcontentandthemainachievementinthispaperincluded：(1)Analyzedtheresearchprogressandexistingissuesl；othinlogisticsdistributionandtheintegrationoflogisticsdistributionandGIS，bymeansofthedetailedanatomyofdistributionoperation，establishedintelligentdistributionsystem．(2)PrimarilyperformedresearchontheCOreissueindistribution,theissueofdistributionscheduling．Tosolvethechoicesofvehicles，thechoicesofcargoloading，therouteplanningofdistributionandotherissues，establishedtheoptimizedschedulingmodelindistributionandals6discussedthealgorithmsusedtosolvethemodel．Itcombinedthegeneticsalgorithmandsimulatedannealingalgorithmtosolvetheissue．Itexperimentallyprovedthatthesolutionisfeasibleandeffective．。(3)InresponsetocurrentGISsoftware’Sdeficiencyinmeetingthecomplexneedsoflogisticsdistribution，thispaperperformedresearchontheintegrationbetweenGISandoptimizedschedulingmodel，presentedapragmaticintegrationscheme，discussedthedetailedintegrationprocessandprovidedanewdistributionschedulingmethod．Moreover,supportedbythisintegrationandmonitoringsub·system，thispapergaveadetailedanalysisofcontrolprocessIJ duringvehicles’on-the·wayprocess-(4)Aftertheaforementionedresearch，onthebasisoftheactuaIdistribu‘ionbusinessofalogisticscoInpanyinNanjingandthebasicgeographicdataofNanjing，tIlispap盯buil‘aprototypesystemofintelligentdistributionandverifiedthefeasibilityofthisre5ea‘ch·Thedesignthinkingandresearchmeth。dhasitsvalueforthereasonahieimplemen‘a‘i∞。fthelogisticsdistributionprocess．Itisabletoimprovetheservicesatisfactionlevelofcustomersandreducetheenterpriseoperationalcosts．Itisconsistentwiththefuturedevelopmentaltrendinlogisticsdistributionservice．Kej．r、vOrds：IntelljgentDistribution；GIS；OptimizedScheduling；Distributi。nDecision；GeneticAlgorithm；SimulatedAnnealingAlgorithmII| 幕干GIS的智能配送系统研究图目录幽1．1车辆调度⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．3图1．2技术路线图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。8图2．1配送级别⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．Il图2-2配送业务总体过程活动图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯13图2．3前台收货业务活动图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯14图2-4调度业务活动图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．15图2．5在途车辆和实时调度业务活动图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．15图2．6信息查询业务活动剧⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯16图2．7统计分析业务活动图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．16图2．8智能配送体系结构图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯17幽2-9智能配送系统主要功能图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯18幽2．10物流智能配送系统体系工作过程示意图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．20圈3．1基本遗传算法流程图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯28图4．1集成过_f!f!图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯40图4．2在途调度策略示意图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯43图4．3新需求调皮示意l刳⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯43图4．4路况变化调度示意图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯44图4．5初始界面幽⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯45图4-6生成后的所有车辆路线图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯46图4．7车辆I的路线规划图⋯⋯⋯⋯⋯。⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．46图4．8车辆2的路线规划幽⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯47图4．8车辆3的路线规划圈⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯47图5一I智能配送管理系统包图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯49图5．2前台受理功能包图⋯⋯⋯⋯⋯⋯⋯⋯⋯．．．．⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯50图5．3调度管理功能包幽⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯51图5．4在途监控功能包图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯51图5·5布洵管理功能包图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．52幽5-6财务管理功能包图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯53VI 摹于GIS的智能配送系统研究图5．7统计管理功能包图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯53图5．8资源管理功能包图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯54图5．9系统设萱功能包围⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯54图5．10物流空间数据的分层方案⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．54图5．1l智能配送系统数据库部分没计示例⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯55图5．12详情单处理界面⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．56图5．13初始调度界面⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯56图5．14参数设置界面⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯57圈5．15生成配送路径界面⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．57图5一16单辆车配送路径界面⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．58图5．17业务查询界面⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯～⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．58图5．18费用对账界面⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．59图5．19统计业务界面⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯59图5，20员工信息界面⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．60图5，2l用户设置界面⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯60VlJ 箍于GIS的智能配送系统研究表目录表1．1算法比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．5表3．2遗传算法编码⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯28表3．3交叉算予类型⋯．⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯29表3．4变异算子类型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．29表3．5客户需求信息⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯34表3-6距离信息(km)⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯34表4．1客户需求信息⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯45 基于GIS的智能配送系统研究学位论文独创性声明本人郑重声明：l、坚持以“求实、创新"的科学精神从事研究工作。2、本论文是我个人在导师指导下进行的研究工作和取得的研究成果。3、本论文中除引文外，所有实验、数据和有关材料均是真实的。4、本论文中除引文和致谢的内容外，不包含其他人或其它机构已经发表或撰写过的研究成果。5、其他同志对本研究所做的贡献均已在论文中作了声明并表示了谢意。作者签名：—皇兰1日期：碰壁：笸学位论文使用授权声明本人完全了解南京师范大学有关保留、使用学位论文的规定，学校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进行检索o．有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适用本规定。作者签名：至军日期：2堂星：≤ 雉十GIS的智能配送系统研究第一章绪论1．1论文选题的背景及意义现代物流作为一种先进的组织方式和管理技术，已经被认为是企业在降低物资消耗、提高劳动生产率以外重要的“第三利润源”。它通过一系列信息技术手段、先进的管理办法和供应链一体化的运作方式，可以降低流通费用，缩短流通时间，整合企业价值链，延伸企业的控制能力，提高客户的满意度，加快企业资金周转，为企业创造新的利润。物流的发展离不开新技术的应用，提高物流领域的信息化、智能化是加快物流业发展的迫切需要。物流配送是物流中一个重要的、直接与消费者相连的环节，配送的目的是为了减少流通环节，降低成本，增强企业竞争力，但是依椎传统的配送方式则不容易达到此目的。从整体来看，国内的配送公司人多是传统的储运公司转变过来的，不仅在技术和观念上难以满足现代配送的需要，而且在配送信息化方面也有待改进。目前，已有的配送管理信息系统只能够为管理者提供普通的业务处理数据和简单的分析数据，不能提供立体化的、多视角的、有渗透力的数据，一些配送决策活动仍然是以人T的经验来决定，包含人量的主观决策成分，如：在配送业务过程中，通常是搬运：】：依据订单将货物装运上=乍，货物上车的顺序和每辆乍的装运数量、货物的摆放位置等都依靠搬运j[的人为经验判断；接着调度、l：作人员依据订单及需求点的位置，指派最佳配送路线或者是司机依本身经验来完成配送。然而，由于配送活动的不断扩张以及路网日趋复杂，以往人工的方式已渐渐不能满足目前的需求，需要相对智能的配送方法米提供快速准确的配乍计划和配送路径规划等配送决策问题，并且实现配送其他环：盼的信息化。在以往的配送方法研究中，问题都集中在配送路线的优化上，但是配送的各个环：17是一个相互影响的有机整体，要实现某个环：1了的最优化，必须将其放在整体中来考虑，在配送路线的规划上缺乏对车辆利用率的考虑，缺少它与前后业务的衔接：另外，在配送调度模型的研究上火部分都是集中住静态模型上，这与现实中动态的实际需求不太符合，不能满足现实不断变化的情况。因此，整体考虑配送全过程，实现配送智能化是有待解决的一个重要问题。配送是将货物从供货点通过运输：l』具运送到需求点的地理空间位置的转移过程，伴随着空间位置的动态变化，是一种典型的空问现象和过程。GIS作为-I'-1关于空间信息处理分析的技术，将其融入到配送过程中。通过GIS与配送模型的集成，可以实现对供货点、需求 皋于GIS的智能配送系统flJi：究点、交通线路等地理信息的提取、加工、分析。实现配送过程的实时动态管理，辅助决策分析等，为配送管理提供新的途径和方法。这样，物流配送企业就能够基丁．属性数据和图形数据的结合进行科学、规范的管理，将从根本上改变传统物流的管理方式和分析模式，具有广阔的虑川前景。将GIS应心。y-物流配送，具有以下儿方面的优势：(1)通过对空间信息与属性信息的一体化管理与综合分析，弥补传统方法缺乏对空间信息管理与分析能力的不足。(2)现代配送的复杂性使得仅依赖传统的运筹学方法无法得出满意的方案，借助GIS的空间分析功能，可提高决策的可靠性。(3)传统物流配送系统仅限于单纯的数据处理利表现，引入GIS可以提高决策的直观性和可视化程度。本文从物流配送企业的实际需求山发，针对目前物流配送的特点，以配送业务过程的信息化、智能化为研究目标，将研究的重点放在优化调度这一关键环节上，运埘数学分析方法、GIS和计算机等技术，建立物流配送的优化调度模型，同时，结合配送的其他业务过程，设计并实现了基于GIS和优化调度模垂4集成的智能配送系统。这对物流配送企业实现智能配送管理，降低成本和提高物流经营管理水平将具有重要的参考价值。1．2国内外研究现状1．2．1物流配送的研究现状物流配送问题可以泛化地拙述为配备最佳运力，选择最优路线，将符合约束条件的物品按照需求者的时间要求从多个起点运到多个终点的问题。但由丁问题的时间、空间、货种、流向、车型等因素的随机性和离散性，为了使问题得剑可行与优化解，从无十年代开始，对配送问题的建模理论与方法、算法与优化、计算模拟等：I：作就一直没有中断过。物流配送涉及到业务运转、运输路线、库存控制等多个方面的内容，国内外许多学者就这类问题的特征进行了分析，并提出了这类问题的数学模型和解决方案。其中，车辆优化调度问题是物流配送优化最为典型的问题，它是物流配送的核心问题，起着关键作用，直接影响到配送成本和服务质量，一定程度上代表了配送的实际运作水平。目前，国内外许多学者都致力于车辆调度f．-I题(VehicleRoutingProblem，VRP)研究，2 荣卡GIS的智能配送系统研究主要涉及模型本身的改进和求解算法设计方面。VFuP是由Dantzig利Ramser于1959年首先提出的，由于这一问题涉及多门学科，应t}fj前景J“泛，很快引起运筹学、麻jH数学、组合数学、图论与网络分析、管理科学与：l：程、物流科学、计算机应用等学科的专家和运输计划制定者与管理者的极人重视，成为研究热点。对车辆调度问题可定义为：对一系列发货点(即配送企业)和收／发货点(即客户需求点)，组织适当的行乍路线，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、乍辆容量限制、j亍驶里程限制、时间限制等)下，达到一定的目标(如路程最短、费川最小、时间尽量少、山车次数尽量少等)(刘明J“‘，2007)。如图1．1所示。‘‘C，一j彳了，。一，’一’0Cj．，’_，厂，￡i’吐。二图I-1车辆调度☆表示陀逆巾心蓝陀送金啵r)衷示霹，’需求点表示_乍辅路径车辆调度问题是一个有约束的组合优化问题，属于NP难题(NondeterministicPolynomialProblem，1『=确定型多项式问题)。Toth等(2002)在其出版的著作中，对VRP的最新研究进展平lJ发展趋势进行了全面的分析：钟彳i泉(2004)研究了多车场情况下的乍辆调皮问题；Svaelsbergh(1985)和Solomon(1986)提出有时限的物流下辆调度问题比一般的物流车辆调度问题更复杂，陈一永等(2005)考虑了带时间窗约束下的配载车辆问题；汗寿阳等(2000)研究了车辆优化调皮问题的分解策略；谢秉磊等(2002)，肖增敏等(2004)先后对动态车辆路径问题进行了总结和展望等等：张建勇等(2006)对具有模型时间的车辆调皮问题进行了研究。按照目前对车辆调度问题的研究性质进行分类，主要包括：(1)按车辆载货情况分，有满载问题(货运量不小于车辆容量，完成一项任务需要不只一辆乍)和1仁满载问题(货运量小于车辆容量，多项任务用一辆乍)。(2)按车场(或货场、配送中心等)数目分，有单车场问题和多车场问题。目前国内人部分研究者都是先将多=乍场化为单车场后用解决单车场的方法进行处理。(3)按：乍辆类型数分，有单下型问题(所有车辆容量相同)和多车型问题(执行任务的车辆的容量不全相同)。(4)按车辆对车场的所属关系分，有布辆开放问题(车辆可以不返同其发车车场)和3 攘十GIS的智能配送系统形f究车辆封闭问题(车辆必须返同其发车下场)。(5)按时间重要性来分，有不带时间窗只考虑空间路线的问题和带时间窗问题。(6)按集、送货性质来分，有单纯的送货、集货问题，也有集送一体化的问题。(7)按优化目标米分，有单目标和多目标问题。由于情况的不同，车辆路线安排问题的模吧构造及算法有很人的差别，一般来说调度问题可以构造成整数规划模型、图论等其它模型。目前国内外用于解决该问题的求解方法主要分为两人类：(1)精确算法精确算法指可求出最优解的算法，耪确算法主要有：分枝定界法(BranchandBoundApproach)、切平面法(CuttingPlanesApproach)、网络流算法(NetworkFlowApproach)、动态规划方法(DynamicProgrammingApproach)。精确算法的计算量一般随问题规模的增火呈指数增长，因此实际应用范同很有限。具体研究成果土要有：Fisher提出的K树法；M．Padberg等的分枝剪枝法；Christofieds等用动态规划放宽空间变鼙解决VRP：LorenaLuiz等对列生成方法的改进等。(2)启发式算法由T-VRP是强NP难题，高效的精确算法存在的可能性不火，所以需要寻找近似算法，在这种背景下，启发式算法成为研究并解决该问题最有效的途径之一。目前已经提山的启发式算法有很多，1967年由Clarke和Wright提山的-IIi约法(SavingMethod)——其原理是通过列出各点对时间的节约量，按：1了约量从人到小构造路径。许多成功的乍辆调度软件就是根据该方法或其改进方法来开发的。李军(200I)针对有时间窗的车辆路线安排问题提出了一种利用‘1，约法的启发式算法，李怡等(2006)也基于：1了约法对配送车辆的路线规划进行了研究。由lin等(1973)提出，并由Laporte等(1992)所推广的分支交换探索法，该算法始终保持解的可行性面义力图向最优化目标逼近。Gillet-p1974年提出的扫描法(SweepMethod)先把：1，点或弧的需求进行分组或划群，然后对每一组问题求解，设计出一条经济的路线。禁忌搜索是对局部邻域搜索扩展后的一种全局逐步寻优算法，该算法由Glover在1986年首次提出，其后很多学者的研究表明该算法的优越性。但是禁忌算法需要的运行时间较长，效率较低。遗传算法(GeneticAlgorithm，GA)是由Holland等于70年代发展起米的，其思想起4 桀十GIS的智能配送系统t／Jf’‘￡源丁生物遗传适者生存的臼然规律，它对优化对象既不要求连续，也不要求可微，尤其适合求解NP．hard问题，目前已经有很多人利州遗传算法求解车辆调度问题并取得了一些研究成果。孙小年等(2007)利朋遗传算法对装卸一体化的车辆路径问题进行了求解，谭前进等(2007)基于遗传算法求解了车辆凋度问题，并将其作为设计和实现物流配送系统的依据；张i杵等(2003)提出一种先Hj优先级综合聚类分析法将客户分类，再J}H带有控制开关系统的改进遗传算法求解多目标VRP的优化方法；张建勇等(2006)将模糊逻辑、模糊控制方法与遗传算法进行有效结合，提山了解决午辆路径问题的一种混合遗传算法；鄢沾等(2004)研究了基于遗传算法的商刚车辆调度策略。此外，还有Metroplis(1953)最早提出，并由Kirkpatrick(1982)应用丁：组合优化问题中的模拟遐火算法，算法的出发点是将组合优化问题与统计力学的热平衡作类比，把优化的目标函数看作能龉函数，模仿物理学中用体物质的退火处理。夏文明等(2007)利川改进的模拟退火算法对1卜满载的午辆调度问题进行了求解，并验证了算法的可行性。阎庆等(2004)、吴升等(2006)、唐勇等(2006)分别将遗传算法与模拟退火算法相结合，对车辆路径问题的求解进行了研究，证明了这种混合算法具有计算效率高、收敛速度快等优点。部分算法的优缺点比较和适用问题如表1．1所示：表1．I算法比较算法优点缺点适用范围动态规划法nT以求衡最优解计算量呈指数增加规模较小的问题分技定界法可以求得最优解计算时间过长规模较小的闯题切、I，面法n，以求樽最优解计算时间过长规模较小的问题节约算法提赢乍辆利用；缸结采小一定最优可解决人规模问题禁忌搜索算法伞局逐步i，优运行时间较K适用于带软时间窗的问题遗传算法全局搜索能力强，时问较少不能保iJE每次搜索结果一样适用f复杂优化模拟退火算法具有随机性结果不一定最优适用于路径改造1．2．2GIS在物流配送中应用的研究现状由于在物流配送分析决策过程中，火量的决策信息与空间地理有关，而GIS具有强火空间数据处理和分析能力，以及独有的空间分析决策功能，GIS可以在物流配送行业中发挥重要的作用，它可以帮助企业处理与地理信息相关的商业数据并辅助配送决策过程，提高物流管理水平及其效率。国外将GIS相关技术戍心于物流配送相关领域的时间较早，目前比较知名的有ESRl公5 堆于GIS的智能配送系统研究司的ArcLogistics；GIS—T(即为运输所JlJ的GIS)软f，l二包；英国的GeoConceptTM和TruckstopTM以及美国的Trip—MakerTM路径优化软什包和互联网上使川的MapxtremeTM，还有关国Caliper公司开发的专供交通专业人士使川的交通地理信息系统软件TransCAD，同样也可以运用到物流配送中(岳维好，2007)。国内已经投放市场的此方面的软件有：奥发公司的“商业送配货地理信息系统”和北大方正的“路径规划系统”，中远的“汽车调度信息系统”等等。这些系统只能满足用户最基本的需要，当问题的约束较为复杂时，这些软件也就显得力不从心了。近年来，国内关于GIS在物流配送{于业中的研究正在不断发展。葛，基伟(2005)建立了基于GIS的配送系统模型，提出了GIS在物流配送中麻心的一些指导方案；李怡等(2006)结合GIS网络分析功能，研究了具有时间窗限制的车辆路线问题，并最终得到了基于实际道路的路线规划方案；吕建升等(2007)介绍了运筹学技术与GIS数据管理结合刚于车辆调度决策；李玲等(2007)介绍了GIS技术应用与物流配送的必然趋势，并对物流配送系统开发的关键技术进行了分析；李军等(2007)对基于Dijkstra算法的优化路径进行了分析，并在GIS平台上付诸实现。然而，国内在这方面的研究还处在一个初期发展阶段，基T-G1S的物流配送系统实际应J{4较少，成功的更少。随着我国现代物流配送的发展，对车辆调度提出了经济性、准时性、灵活性的综合要求，这就需要我们针对我国的物流配送实际情况，借鉴国外的研究成果，将GIS与高效、可行的配送调度算法模型相集成应明，从而推动我国配送事业的发展。1．3存在问题分析(1)现代配送更强调配送系统中各个环节的协调性，但目前研究中缺少从系统的角度对配送过程的整体策略的研究，无法体现配送业务问的关联性以及实现配送过程的智能化。更重要的是，在已有的配送管理信息系统中，配送过程的决策主要还是依赖于人1：模式，包含了大量的主观决策成分，成为制约配送企业发展的瓶颈。(2)GIS专长于管理空间数据与属性数据，对配送管理有着重要的意义，但是目前基于两者结合的研究尚显不足，且多基于简单的距离最短模型。由于实际物流配送的网络分析情况复杂，目前GIS软件的网络分析功能无法满足现实需求。因此，需要根据物流配送特点，制定适合配送企业实际需要的GIS网络分析功能。6 皋于GIS的智能配送系统研究1．4研究目标、内容与技术路线1．4．1研究目标、研究内容本文的研究目标是为了满足物流配送企业的实际需求，构建一个物流智能配送系统，通过对物流配送作业流程的分析和研究，基丁．GIS技术解决配送调度决策分析这一关键性问题，同时，结合配送的其他业务过程，设计和实现物流智能配送系统，为物流配送企业提供智能化、决策化支持。本文的研究内容主要分为以一FJL部分：(1)物流智能配送的优化调度模型建立对配送的运作方式和业务过程进行详细的了解，对配送的合理化做出分析，构建智能配送业务模型。从配送全过程出发，考虑配送时间段、货物量、距离等因素，实现对车辆配送路线的规划；考虑货物剑达需求点的顺序、货物的重量等因素，实现乍辆货物装载的优化。(2)模型与GIS的集成对GIS与配送调度模型的集成方法进行研究，通过已有算法来扩展GIS在物流配送的网络分析功能，得剑满足配送实际需要的网络分析功能，实现配送核心问题——车辆调度的优化解决方案。(3)智能配送系统的实现在优化调度实现的基础上，设计智能配送系统框架，设计系统各个子模块的详细功能，设计系统所需的数据库，实现对配送业务过程的智能化决策和信息化操作。1．4．2技术路线本技术路线的制定是在充分研究国内外研究现状，对系统的理论可行性与技术可行性进行充分论证的基础上，紧紧同绕实现论文研究目标制定的。(1)首先对国内外相关文献进行检索和阅读，这类文献主要包括：配送系统、车辆调度、基于GIS的配送管理、启发式算法等方面的相关论文，分析相关问题的研究现状：(2)充分分析物流配送业务过程、理解物流配送知识，找出实际应用和研究中存在的问题，提出物流智能配送体系的设计思想；(3)构建配送管理的优化调度模型，解决车辆选择、装载货物选择、配送路线规划问7 雄十GIS的智能百已送系统40D't；题，并基于遗传算法和模拟退火算法的结合，对优化调度模型进行求解，检验其可行性。‘，(4)对优化调度模型与GIS的集成进行研究，从数据集成——物流配送信息和地理数据的集成，功能集成——乜lS基本功能和配送调度决策分析功能的集成，探讨其集成模式。(5)通过系统的各个阶段设计，实现物流智能配送系统的原型系统。叵圣亟臣燮狴型I针对物流配送业务，总结目前研究：■的存在问题广——～——————J——一———]；确定智能配送体系的设计思想IJ物流智能配送系统的IT设计与实现图1．2技术路线图1．5本文研究的内容与组织第一章绪论。介绍本文选题的背景和意义、国内外物流配送的研究现状和GIS与物流配送集成的研究现状，从中揭示目前研究中仍然存在的一些问题，针对这些问题给出了本文的研究目标、研究内容和研究采用的技术路线。第二章物流智能配送。阐述配送的特点、配送原则和影响配送的主要冈素，针对国内中小型配送公司的具体作业过程分析配送的各业务流程，在此基础上，提出智能配送体系的研究思路和智能配送系统需要实现的几火主要功能。第三章物流智能配送的优化调度模型研究。针对物流配送中的核心决策问题，构造配送的优化调度模趔，解决带时间窗的多车调度问题，提山基丁．模拟退火遗传算法的详细求解过程，并进行实例分析，验证算法的可行性和有效性。8 皋千GIS的智能酣送系统ffJf究第四章优化调度模刑与GIS的集成。针对GIS和配送优化调度模型的集成问题，从数据集成和功能集成两个方面，形成集成模式利在途调度的策略，并进行模拟集成的实例分析。第五章物流智能配送系统的设计与实现。针对配送业务的全过程，以乍辆调度决策的实现为基础，设计智能配送系统的总体框架和系统各个模块的详细功能，实现原型系统。第六章结论与展望。对论文的研究‘l：作进行了总结，并对-T作中存在的一些问题与今后进一步的研究方向提山了设想。9 皋于GIS的智能配送系统研究2．1物流配送第二章物流智能配送2．1．1配送概念与特点(1)配送的概念配送是在小范嗣内以最小成本，为分散在不同地方的多位客户少量、高频率地运输货物。中国国家标准《物流术语》中将配送定义为：“在经济合理区域范同内，根据_Hj户要求，对物品进行拣选、加]：、包装、分割、组配等作业，井按时送达指定地点的物流活动”。从配送活动的实施过程上看，配送包括“配”和“送”两个方面的活动，“配”是对货物进行集中、分拣和组配，“送”是以各种不同的方式将货物送达至指定地点或客户手中。(2)配送的特点配送是物流中的一种特殊的、综合的活动形式，儿乎包括了所有的物流功能要素，是物流的一个缩影或在某小范围中是全部物流活动的体现。一般配送集装卸、包装、保管、运输于一身，通过这一系列活动完成将货物送达的目的；特殊的配送则还要进行加，【：活动。它的目的指向是安全，准确、优质服务和较低的物流费J|J。①它是配送、配货、分货、送货等活动的有机结合体。配送是以分拣和配货为土要手段，以送货和抵达为目的的一种特殊的综合物流活动。其特殊性表现在它包含了某一段的装卸、包装、流通加工、保管等活动，但又不是这些活动的全部或全过程。因此，配送不能简单地等同于运输或其他物流活动的全部。②配送的概念描述了接近用户资源配置的全过程。配送不仅是在恰当的时间、通过恰当的方式、以恰当的费H』将物品最终传递给需求者，而且将最优质的服务传递给需求者。因此，它一头连接着物流系统的业务环一饥一头连接着消费者，直接面对服务对象的各种服务要求。配送功能完成的质量及其达到的服务水准，虽直接而又具体地反映了物流系统对需求的满足程度。③配送是～种专业化的分工方式，是火生产、专业化分丁：在流通领域的体现。一般的送货目的仅仅在于多销售一些物品，而配送活动已经上升为营钔活动的重要手段。准确而又稳定的配送活动可以在保证供给的同时，最人限度地降低生产或者流通企业的物nl-n!件。存，从IO 烬千GIS的智能配送系统研究而降低了总的销售成本。(3)配送的级别根据配送的区域范R司，可以将配送分为一级配送，二级配送。如图2—1所示，物流配送中心到各网点的配送为一级配送，网点到客户点的配送为二级配送。_二jo：j：吐jI。、2．1．2配送原则’L．Cj7‘，～—赢1幽2．1配送级别贸表示物流配送中心口表示配j羞Ifl心的荇刚点，二)表示客户点配送调皮足否合理对配送成本、效益的影响很人，冈此，优化调度方案是配送业务过程中非常重要的一项’I：作。为达剑配送合理化的要求，在日常的配送作业中应该遵循一定的优化原则：(1)效益原则：在选择效益为原则时，一般是以企业当前的效益为主要考虑冈素，同时兼顾长远的效益。效益屉企!比整体经营活动的综合体现，可以用利润米表示，冈此，效益原则是以利润的数值最人为目标的。但由丁：效懿是综合的反映，在拟定数学模型时，很难与配送路线之间建立函数关系，一般很少。(2)准时原则：配送中心必须要在客户要求的送达时间内将货物送到客户订单上所要求的送达地点，既不能晚于最迟送达时间，也不能早于最早时间。(3)最短路原则：能够按照展短路径，对所有的客户订单进行综合考虑，即一车装多个客户点的货物情况下，车辆的行驶路径的总距离是最短的。(4)成本原则：计算成本比较困难，但成本和配送路线之间有着密切关系。在成本对最终效茄起作用时，以成本最低为目标实际上就是选择了效益为目标，但却有所简化，比较实用，冈此是可以采HJ的。需要注意的是，有时候路程最短并不见得成本就最低，道路条件、道路收费等因素也影响着成本。(5)满载原则：能对物流中心的所有车辆进行管理，根据订单要求合理选出所需的车 堆-I二GIS的智能酣送系统fiJf究辆类别，找山发印时的待运营的车辆进行装卞，还要保证满载率越高越好。2．1．3影响配送的主要因素物流配送的终端业务环节实际是一个涉及多种影响闪索、多个目标要求的运输问题。影响物流西己送的主要冈素包括：道路网结构、运输．J：具、运输环：1，、运输时间和运输成本。(1)道路网结构道路网是实现货物异地转移的基础设施，是配送业务中形成货物通达能力的决定性冈素。道路网的覆盖范同、连通性以及路网中的路况水平是决定道路网结构的主要冈素。根据配送任务的范同可以将道路网划分为不同的层次，如全国干线网、省内网、地区网以及支线网等。干线网主要面对全国各人、中城市间的货物运输，省内网则主要面对省内人、中城市问的货物运输。(2)运输：J：具运输一L：具是实现货物异地转移的载体，它以交通网络为基础。目前我国的干线运输土要依赖于火车、飞机，区域性运输则主要依赖汽车、火车、轮船等。不同的运输。【：具有不同的运输能力指标，如速度、容量等，也有不同的成本消耗。本文中的配送研究只是针对汽车的。(3)运输环。肖每增加一次运输，不但会增加起运的运费和总运费，而且必须要增加运输的附属活动，如装卸、包装等，各项技术经济指标也会因此下降。所以，减少运输环。忆尤其是同类运输工具的环节，对合理运输有促进作用。(4)运输时间运输是配送过程中需要花费较多时间的环节，尤其是远程运输，在全部配送环节中，运输时间。圩绝大部分，所以，运输时间的缩短对整个流通时间的缩短有决定性的用。此外，运输时间短，有利于运输车辆的加速周转，充分发挥运力的作H】，有利于企业资金的周转，有利于线路通过能力的提高。(5)运输费用运输费用是影响物流配送的一个重要指标。运费在全部费JH中11■艮人比例，运费高低在很人程度决定整个配送系统的竞争能力。实际上，运输费用的降低，无论对客户来讲还是对物流配送经营企业米讲，都是配送合理化的一个重要目标。运费的判断，也是各种合理化实施是否行之有效的最终判断依据之一。12 基于GIS的智能配送系统研究冈此，合理使HJ运输J：具，优化运输环：1了，正确安排运输时间，有效降低运输费朋，是配送管理要实现的重要功能。2．2物流配送的业务流程不同类型的配送公司。配送的业务流程各有特点，但是其中涉及的几个主要业务过程是人致相同的。这里提供的只是一个简化的配送业务总流程，它是主要针对国内几个中小型配送公司的业务流科提炼而成。2．2．1总流程概述配送业务从客户委托配送任务开始，前台受理员进行接单处理，并在得王0客户的最终确认后将信息通知后台调度中心安排车辆；调度员根据信息内容及系统提供的各种可调度车辆的信息，确定一个发车安排(车辆的装载计划和行驶路线规划)；并对在途中的=乍辆、货物情况进行监控：货物到达送货地点后，收货人检布验收完毕后进行确认签收。总的配送业务过程如图2．2所示：图2-2配送业务总体过程活动图13动态丈时凋度 2．2．2各子业务流程(1)前台收货业务前台负责业务的受理和记录登记，受理方式包括霹户上门、客户的网上订单、电话通知、传真、委托15受理等形式。前台根据客户二旧面的或口头的描述，记录‘卜．货物的名称、重量、体积、什数、收货人信息、发货人信息、货物的送达时间要求等，并确定费j|J和付款方式。。前台收货业务过程如图2．3所示。图2-3前台收货业务活动幽(2)集货业务将分散的或小批量的物品集中起来，以便进行配送的作业。(3)配送调度配送调度作业环节是配送业务的重要决策环：m它是指住客户需求已知的情况下，确定车辆在各个客户间的行程路线，使得运输路线最短或运输成本最低，它直接影响剑配送的效率，服务质量和配送成本。根据客户货物量人小的不同，调度可能是安排多辆车为一个客户服务，也可能是安排一辆卞为多个客户服务，这就是满载调度和1F满载i用度的问题。满载调度的情况相对简单一些，配送过程是从一个起点到一个终点，考虑的冈素较少。而1F满载时，即当单个客户配送数量不能达剑车辆的有效载运负荷时，就存在如何集中不同客户的不同货物进行搭配装载，以充分利刚运能、运力的问题，这就需要配载：同时也要考虑各个午辆路线的安排问题，使得配送满足客户需要和费J{j最低化。配送车辆在配送出发前，通过基。T-GIS的分析和辅助决策，并辅以配送区域、配送的多个目的地、城市交通线路等情况，根据配送调度模型生成初始的调度方案，其过程如图2．4所示。14 綦十GIS的智能配送系统研究图2-4调度业务活动图(4)车辆监控和实时调度午辆配送过程的监控与信息及时反馈，是客户和配送公司的共同需求，也是实现动态调度的前提条件。在配送车辆的行驶过程中，调度监控中心可以根据由GPS组成的全程跟踪网实时掌握下辆的行驶情况、配送过程等，当山现新的客户需求，调度中心可以根据车辆实时信息安排最近的乍辆进行任务处理：如果车辆发生偏离路线、停滞、超速等现象时，调度监控中心会立即收剑报警信息，并进行调褴。通过对乍辆的监控，同时也实现了对下载货物的监控，不论是客户还是管理人员，都可以随时布询货物的状态，实时了解情况。对在途乍辆和货物的管理过程如图2．5所示。羁驶见执行陀送任务乍辆舱控)(货物跟踪】(驾驶员监控I乜r地罔珏示．信息反馈l出现祈需求或特殊情况——JL—一、调度中心动态调度l、-—-————，————————√————正——、、牛辆路线蹦部调整1图2-5柱途车辆和实时调度业务活动图15 堆十GIS的智能配送系统liJ『究(5)到货交接配送下辆按要求将货物运至目的地，收货人核查实际剑货数鼙、质餐，确定井签收。进行联运时，货物只是交给下一个承运人，由承运人根据配送公司的返单合同要求送到目的地。(6)信息查询当客户询问货物情况或到达状态时，受理人员根据客户详情单的惟一识别号进行快速查询，详情单号遗忘或丢失情况下还可根据货物其他内容进行多内容详细奄询。查询结果返回货物的历史状态和各阶段完成时间，信息查询过程如图2-6所示。图2-6信息查询业务活动图(7)统计分析负责对公司业务涉及的费州和业务量的统计，即对货物量、货物配送过程涉及的不同费用明细分别进行统计。统计分析的主要业务过程如图2．7所示。图2．7统计分析业务活动图2．3物流智能配送体系2．3．1智能配送体系随着大批量、少批次的物流配送活动逐步被小批量、多批次所取代，个性化、多样化的市场需求越来越II有更多的市场份额，配送已成为物流活动的中心环：17和最终目的。因此，物流企业内部的所有部门和人员都要做到面向配送、面向市场、面向客户，这就需要一个完16 幕十GIS的智能配送系统研究善的物流运作模式，一套信息化的配送优化系统。物流智能配送体系就是指根据配送企业的业务运转过程，运用GIS技术、计算机技术、调度优化模型、数据库技术等，依托高精度电子地图，对物流配送业务进行业务受理管理、优化调度分析、可视化凋度、报表输出、业务夯询、统计等一体化操作，而建立的信息化、智能化的新型配送系统，旨在降低配送成本．提高客户服务水平，减轻调度人员：【作强度，满足城市配送快速发展的需要。其体系结构图如2．8所示。图2-8智能配送体系结构图与现有的配送方式相比，智能配送体系的优势和社会经济效益土要体现在：(1)合理化管理，减轻调度人员和司机的多}动强度：(2)合理化凋度，降低配送成本；(3)及时满足客户需要，提高物流配送的服务质量，实现物流配送服务的准时性、准确性和专业性；(4)提升：I：作效率，缩短总体配送时间(调度时间+送货时间)；(5)提高物流企业的决策分析能力，进而增强企业的核心竞争力；(6)降低全社会的物流成本，具有巨大的社会经济效益；2．3．2智能配送系统需求分析智能物流配送系统通过计算机实现对配送业务的信息化处理：将前台受理业务中收集到的信息进行汇总整理，存储在数据库中；每天对当日需要配送的对象自动生成任务调度提示．在调度过程中根据数据库中需要调度的货物信息生成最佳调皮方案，实现车辆装载、行驶路17 綦于GIS的智能配送系统川究线的统一安排；下辆执行任务时对其进行监控，并进行实时动态调度，满足现实需求的变化。从配送业务流程的分析中，可以提炼山智能配送系统需要实现的儿人主要功能，如图2-9所示。，，，费J|iid隶按客，·黻姘、、r度、—J√／＼图2-9智能配送系统主要功能I!}l(1)配送信息资源收集处理：系统可以通过前台受理、网上订单等多种途径收集客户信息，包括上门取货信息、送货信息等。这些信息经过确认厉¨1类整理，确定信息类别，系统根据不同信息类别的处理过程将信息分发到不同的职能部fj，其中入量的信息被使用在调度管理中。(2)优化调度管理：包括配载和配送路径的优化。配送业务要求按时或尽快的将货物交到客户手中，而货物的配载和送货路径的规划是配送业务的重要部分。货物配载和送货路径的规划是紧密联系在一起的，货物配载必须根据下辆的装载能力和币辆的行驶路径来分配，而车辆行驶路径是根据各种需求信息分析出的车辆最佳执行方案，确保配送车辆的装载率较高，且配送在满足客户需求的情况下配送成本最低化或综合目标最优化。(3)实时监控调度管理：通过6IS、GPS等技术，将道路信息、车辆信息和行驶信息进行收集、储存、处理，随时获知正在执行任务的所有车辆的情况，帮助调度监控人员对车辆进行实时调度管理。(4)对客户进行服务：建立完善的客户管理模块，将客户的相关信息：详细地址、单位、电话、手机等存入数据库中，建立客户档案，对各类信息存储、分析，方便以后改进作业流程，提高顾客的满意度。(5)费用财务的管理：收集到客户委托配送信息后，根据货物的重量、货物的性质、18盘一信一息户一之兰客～物旱套k 耩于GIS的智能配送系统研究路程的远近，确定对客户收取的费JIj总和，并对费川信息进行保存，为以后的财务汇总，查询等做准备。(6)公司资源管理：管理配送企业的7F辆，对车辆的运力、载重、下型等信息进行管理；对公司员。r=、管理人员进行信息管理。(7)其他：如系统各类参数的设置；系统各类报表、清单信息的输出、传输及打印。智能配送系统中优化调度的设计过程为：从前台收货模块(或网上订单模块)得到配送货物的相关信息，存入指定的数据库中，然后可以通过人为添加或系统白动批次提醒两种方式，来通知调度人员当日需要进行调度配送的任务需求等信息；(1)调度中心人员根据物流智能配送系统提供的目前可以使用的车辆运力，及货物运送量，在调皮模块生成配载方案和初始配送路线安排。首先将超过或达剑乍辆载重的人宗货物以直送方式处理，接着将剩下的零散部分转入多点配送方式，打印山相应的配载和配送单据，以便司机根据系统生成的优化调度方案执行调度任务；(2)对行驶中的乍辆进行实时监控，查看车辆执行任务的情况：(3)前台接收到新的提货需求，调度中心在实时调度策略模块下，对当前行驶中的车辆进行分析，奁找是否有下辆可以执行当前的提货需求，有则通知调整该卞路线，无则安排新车辆执行或者放弃本次任务。整个物流智能配送系统体系：I：作过程如图2—10所示：19 挂于GIS的智能配送系统fiJf究2．4本章小结图2．10物流智能配送系统体系丁作过程，J：意图配送是物流系统的一个关键环节，它涉及剑收货、集货、配载、配送等一系列作业，本章通过对配送概念的介绍，分析配送合理化的原则，总结了合理配送的几个土要困素，并对配送公司的业务流稚进行了详细剖析，从中提出了物流智能配送体系的架构思路，进行了物流智能配送系统的需求分析。20 苯十GIS的智能配送系统研究第三章物流智能配送的优化调度模型研究物流配送中最经典的问题之一就是车辆调度问题，它是指在客户需求位置已知的情况下，确定车辆在各个客户间的行程路线，使得运输路线最短或运输成本最低，它直接影响到配送的效率，服务质餐和配送成本。车辆调度问题是一个NP．hard问题，它是学术界和产业界十分关注的热点利难点问题。冈此在智能配送系统中，实现优化调度也是整个系统的核心部分。随着物流配送集约化、一体化的发展，常将配送的各环节综合起来考虑，核心部分为配送车辆的集货、货物装配及送货过程。进行配送系统优化，主要就是指配送车辆的优化调度，包括车辆选择优化、装载货物选择优化、配送路线规划优化，以及三者一体化的优化。在处理该问题时，可以根据配送调度不同要求的目标函数(例如运距最短、配送时间最短、运输费用最少等)，将调度问题¨-]结为表述问题的数学模型，然后用计算机求得合理可行的优化方案，在配送运作中付i者实施。3-1调度问题的分类绪论中已经对不同情况的乍辆调度问题进行了多种分类，本章讨论采川一种通川的方式，比如有时问窗的可以包含无时间窗的，考虑集送货情况可以包含单纯的集货或送货臀，将调度过程分为直送式(点到点)调度、多客户点(一对多)调度、在途配送调度。3．1．1直送式配送调度当某个客户的货物量过火，超过单辆车的最犬载重能力时，即车辆满载情况下，采用直送式配送。如果乍辆满载后仍有多余的货物，则将多余货物部分划入多点配送调度中去。直送式配送问题描述为：一个配送企业，只对应一个客户点来进行配送。配送分两步执行：第一步7F辆选择，根据配载货物的重量和类型来选择车辆，一般对于城市物流配送，小型车即可满足：第二步路线选扦，给不同的道路(例如道路的乍流量、等级、滞留时间不同等)给予不同的加权系数，求取最短路径即可实现。最短路径方法利用GIS软件中白带的最短路径功能直接实现。在此不作为本文主要讨论的对象。2I 雉于GIS的智能配送系统研究3．1．2多点配送调度多点配送即一个配送企业对应有多个需求点(客户点)的状况，当客户数毓较多，各客户所需货物量不人的情况下，就需要对多个客户的货物进行装载配送。它需要考虑到多种约束条件，合理选择币辆，实现货物的有效有序装载，生成车辆的优化行驶路线。这是本章主要讨论对象。3．1．3在途配送调度在途配送凋度问题属于一种信息动态变化类型的问题，信息变化考虑的内容主要有：道路情况的变化、客户信息(客户的更新或缺失、货物需求量、送货时间、送货地点)的变化、车辆和司机的突发情况的不确定性。考虑变化内容越多，优化调度问题的求解就越复杂。但当信息一旦明确已知，可以把动态车辆调度问题转化为静态下辆调度问题米求解。在初始调度方案上，根据新情况新需求的信息，局部调整车辆的行驶路线，进行实时动态的调度管理。在途配送调度需要基于GIS技术，在监控系统的支持下来实现，将在第四章对其进行详细的分析。3．2优化调度模型基本结构物流配送车辆调度问题的构成要素主要包括货物、布辆、配送企业(配送中心)、客户、运输网络、约束条件和目标函数等。(1)货物货物是配送的对象。可将每个客户需求(或供应)的货物看成一批货物。每批货物都包括名称、性质、包装、重量、体积、要求送到(或取走)的时间和地址等属性。在本系统中未考虑货物的互斥性。(2)车辆车辆是货物的运载工具。其主要属性包括：午辆的类型、车辆的最人载重、车辆的装载容积、车速等。车辆的类型有通用和专用之分。其中，装载量和装载容积属性，是进行车辆装载决策的主要依据。(3)配送中心配送中心是指进行集货、配货、配装、送货作业的指挥中心地。在不同的配送系统中，22 皋十GIS的智能配送系统研究配送中心的数譬可以只有一个，也可以有多个。同时，对于某个配送中心，其供应的货物可能有一种，也可能有多种。(4)客户客户是指货物的需求方或供戍方，可以是一般用户，也可以是下属仓库、零售商店等。客户的属性包括需求货物的数量、需求货物的时间、需求货物的次数及需求货物的满足科摩等，其中，客户对配送时间的要求可分为以下几种情况：①无时间限制；②有时间限制，并要求只能在指定的时间(也称为硬时间窗)内完成任务：③有时间限制，但可以不遵守(也称为软时间窗)，只是违反时要给予一定的惩罚。(5)运输网络运输网络是由顶点(指配送企业、客户)、无向边和有向弧(道路)组成的。边、弧的属性包括方向、权值和交通流链限制等。某运输网络中可能仅有无向边：也可能仅含有向弧；还可能既有无向边，又含有向弧。运输网络中边或弧的权值可以表示距离、时间或费用。边或弧的权值变化分为以下几种情况：①同定，即不随时间和车辆的不同而变化；②随时间不同而变化或者随下辆的不同而变化；③既随时间不同而变化，义随车辆不同而变化。(6)约束条件配送：乍辆调度问题的约束条件主要包括：①满足所有客户对货物^^种、数量的要求；②满足客户对货物剑达时间范罔的要求：③车辆在配送过程中的实际载货量不得超过车辆的最大允许装载量和车辆容积；④在配送企业现有运力范用内；⑤在道路通过允许的条件F。(7)优化目标对配送车辆调度问题，可以选用一个指标，也可以选用多个指标。经常选用的优化目有：①配送的总距离最短。配送里程与配送乍辆的耗油量、磨损程度以及司机疲劳程度等直接相关，它直接决定运输的成本，对配送业务的经济效益有很大影响。由于配送距离计算方便，因此，它是确定配送路线时使川最多的一个指标。②配送车辆的利川率最人。即将配送货物的重量、体积与车辆的载重量和载重体积结23 皋十GIS的智能配送系统Ⅲ究合起来考虑，以所有配送乍辆的空间利Hj率或载重利刚率最人为目标(一般为载重利川率)。⑨综合费川最低。降低综合费川是实现配送业务经济效i；；i的基本要求。在物流配送中，与取、送货有关的费用包括：车辆维护和行驶费用、道路交通管理费、货物装卸费川、有关，人员T资费用等。④准时性最高。在现代配送业务中，很多客户对交货时间的要求越来越严格，为了提高配送的服务质量，很多配送企业都已将配送准时性最高作为确定配送路线的目标。3．3优化调度模型的构造3．3．1物流配送调度问题界定从前面的分析中，可以看出，现实中物流配送企业的车辆调度作业很复杂，它涉及多方面的约束条1；，J：与川户需求，包括货物需求量、发送量、下辆容鼙限制、时问限制等等。根据这些分析，本文对优化调度问题的界定如下：在一个存在供求关系的系统中，有一个配送企业、若干个客户，该配送企业配有若干辆车，在营业时间内，配送企业对一定区域范嗣内的客户进行物流配送服务，根据客户要求向货物需求点执行配送任务。车辆从配送企业出发依次访问各个客户，每辆印的一次载重量不能超过其额定载重量，且每个货物要在客户要求的时问范同内得到配送．要求合理调度乍辆，安排车辆装载和车辆的出行时间及行乍路线，使整个配送过程实现优化。3．．3．2模型构造为建立接近实际情况的物流配送车辆优化调度模型，本文在前人研究的基础上建立了含有时间窗和容量、体积等约束的综合优化调度模型。问题的基本假设为：在配送企业位置、需求点位置和道路等已知的情况下。对历辆乍，疗个客户点，确定乍辆分配(每辆乍负责的客户点)及每辆午的行驶路线，同时满足下列条件：(1)所有车辆路线的起始点和终止点都是配送始发点0．(2)每个客户有一个非负的货物需求量；(3)一辆车可以为多个客户服务；(4)每辆乍要在客户要求的时间范围内送剑各客户点。24 堆十GIS的智能配送系统研究变量和参数符号说明：T／：表示配送需求点的数目(即客户点)：i，J：均表示下辆需要经过的某个客户点(‘-『=0，I，2，3⋯")：其中，将配送企业看作一个特殊客户点，当i=0或J=0时，该点表示为配送企业点：乜表示执行配送任务的某一辆车(七=1，2⋯．，K)：K：表示使川的车辆数目：g』：表示客户点f的货物重鼙；Ⅵ：表示客户点i的货物体积大小：【E正，￡乃】：为客户点f要求货物送到的时间范同(其中，E乃为最早到达时间，￡瓦为最晚至0达时间)；ST,：表示车辆在客户点朋艮务的时间，通常服务时问与客户点f的货物堵有关系，为方便表达，本文以正比关系表示两者的关系；Qk：表示午辆七的最人载重，为方便计算，可将车辆看为同一型号的下，载重力相同：圪：表示车辆k的最人体积容量，同一型号的：乍辆，其体积容量相同；Co：表示客户点i到客户点，的运输成本(它也可表示为客户点i至-IJj的运输距离、运输时间等，但通常认为运输成本是与运输距离成一定比例关系，冈此，本模型中直接以距离表示米说明问题，即f到／的距离与。为l：1关系)，而当f=，时，CO=D；S：车辆到达客户点f的时间；w，：车辆剩余载重的惩罚系数；W2：早到等待的惩罚系数：Wj：迟到的惩罚系数；b：装卸耗时与货物量的比率关系，b>O。数学模型：minZ=砉喜嘉c以+w，砉喜cG吨¨‰：扣nc¨洲批喜m吣嘲渤】(1)其中：‰=1或0(2)肌，=1或0(3)杰M，≤Q。(4)∑Yb'，，≤吒J=IST,=bqi25(5)(6) 龌十GIS的智能配送系统fiJf究K≤历(7)模型说明：式(1)为目标函数，它将各项最低化目标综合进行考虑，包括距离最少化、空载率最低化和配送时间最准时化：其中争争争cx，。表示车辆运输距离或运输成本，这与q所代表的意义相关(为消‘一厶‘一v一帅7+’。’’晰的说明问题，本文直接以cf，表示f到，的距离进行问题研究)；．W．I羔窆(已一叮肌)表示车辆的剩余载重代价；w2窆Imin(s．Er,，o)I批主ma)【(s．Lr,，o)表示车辆剑达每个客户点，的时间，应该在客户f要求的时间范围[ET,，LT,】内到达，否则对其进行惩罚，当惩罚系数为无穷人时，即为硬时间窗问题，表示不满足时间要求的话，即为不可行解。式(2)～(7)为模型的约束条件：式(2)表示车辆k是否从客户点i处行驶至客户点，处，如果是!J!IJ为1，否则为O：式(3)表示客户点f的货物是否由车辆七来运输，如果是则为l，否则为O：式(4)表示车辆七运输的货物重量总和不能超过车辆七的最人载重能力；式(5)表示印辆七运输的货物体积总和不能超过午辆七的体积装载能力；式(6)表示车辆七在客户点i停留的时间，与该客户的货物需求鼍成止比：式(7)表示使用的：乍辆数目K应不超过配送企业的现有乍辆数目朋。该模型具有一定的通川性，根据现实中不同的需求情况，可以对目标函数中的惩罚系数进行相应的设置，将其转化为不同类型的问题。即对w，，w2，W3的值根据追求的目标不同，进行改变。其中，当w，，w^w3极小时，目标函数可以简化为minZ2圭窆窆巴x帕(8)k=i●=¨J=0当w』，w2，w3极人时，目标函数可以简化为minZ3w，壹窆(Q^一口肌)|tw,杰．1rain(8,一￡巧，o)f+％喜max(墨-tT,，o)】‘9’具体的参数设置需根据具体应用的要求来设定。随着越来越多的客户对物流配送企业提出JustInTime的配送要求，是否能做到准时配送成为考夯现代配送企业服务水平的一项重要指标，囚此，客户所提出的时间表，成为配送企业对配送车辆制定调度计划的重要依据，本文后面也以带时间窗的优化调度模型进行分析。26 罐十GIS的智能配送系统研究3．4算法设计与实现3．4．1求解思路许多学者对车辆优化调度问题的计算复杂性进行了研究，车辆优化调度问题已被证明为NP难题。因此，在解决实际问题时，高效的精确算法存在的可能性不人，目前多以启发式解法来求解。遗传算法就是其中一种很好的解决方法，它对于复杂的组合优化问题具有较强的寻优能力，已经有不少人利刚遗传算法来求解车辆调度问题并取得了一些研究成果。但是在针对具体的问题时，遗传算法中采朋的算子帚l具体步骤是存在差异的。本文在前人研究基础上。采圳模拟退火遗传算法进行求解：L作：基于简单遗传算法的思路，采刚针对物流配送特点的白然数编码、改进交义算子、变异算子的遗传算法，用于求解优化调度问题，并将模拟退火的Metropolis接受准则引入遗传算法的群体更新阶段，克服遗传算法应用中的甲．熟收敛现致，提高搜索效率。主要分以下三步来求得优化调度问题的满意解：(1)把配送企业作为一个特殊的客户米处理。求出配送网络中任意2个客户问的最短距离，进而求出运输成本G(本文中直接川G表示距离)：(2)采HJ模拟退火遗传算法求山午辆的分配方案；(3)求解每辆下的线路安排。3．4．2模拟退火遗传算法3．4．2．1遗传算法遗传算法的基本思想是借鉴优胜劣汰、适者生存的自然选择和自然遗传的机理，其本质是一种高效求解问题的全局搜索方法。它能在搜索过程中白动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。将其应用于实际问题求解，通常的步骤包括：(1)寻找有效且通J}J的编码方法，将问题的可能解直接或间接地编码成有限字符串；(2)确定遗传算子的类型，选择所使用的操作算子，主要包括选择、交叉、变异等：(3)对操作算子选择其符合实际优化问题的模式，如选择的模式、交叉的模式、变异的模式等等，然后加以没计；(4)确定算子所涉及的参数，如群组的人小七、交叉概率只、变异概率厶等；27 肚十GIS的智能配送系统IiJf究(5)根据编码方法和问题的实际需求，定义或设计一个适应度函数，以测量评价各个解的性能的优劣；(6)确定算法的收敛依据；(7)根据编码方法，设计译码方法。基本遗传算法的主要流稗如图3．1所示：图3-I基本遗传算法流程图遗传算法开创至今，取得了长足的发展，已成为信息科学、计算机科学、运筹学和应用数!!；乏等诸多学科所共同关注的热点研究领域。为了提高遗传算法的性能，克服其在解决实际，问题中遇到的凼难，近年来学者做了大量研究，在算法设计和执行策略方面有了很人进展。(1)编码方法遗传算法主要是对群体中个体施加操作，从而完成优化的，但是遗传算法不能直接处理问题空间的参数，只能处理基冈链码形式表示的个体。冈此，要使川遗传算法，就必须把优化问题的解的参数形式转化成基因链码的表示形式。这一转换操作叫编码，也可以称作是问题的表示。目前，针对不同的求解问题，主要的编码方式有二进制编码、格雷码、动态编码等，它们各自的特点如表3．2所示。表3-2遗传算法编码编码方法特点二进制编码优点：编码解码简单，交叉变异等遗传操作便于实现；缺点：局部搜索能力较差，对于复杂问题件能较低格雷码格雷码足将二进制编码通过一个变换所得到的编码，提高了遗传算法的局部搜索能力动态编码动态编码足当算法收敛到某局部檄值时减小搜索I_)(域，增加搜索的精度。实数编码为丫克服二进制编码的缺点，采用十进制进行编码直接对觯进行遗传操作，从而便于0I入与问题领域相关的启发式信息，以增加遗传算法的搜索能力有序串编码对很多组合优化问题，I：1标函数的值不仅与表示解的亨符串中’，符的值有关，而且与j￡所在字符串的位置钶关。这样的问题称为排序问题。(2)适应度函数遗传算法在优化搜索中基本上不用外部信息，仅用适应度函数为寻优依据，利用种群中 基于GIS的智能配送系统研究每个个体的适应度值来进行搜索。一股适应度函数直接为目标函数或由目标函数变换而成。(3)选择机制选择是遗传算法中最主要的机制，也是影响遗传算法性能最主要的冈素。选择过程的第一步是计算适应度，在被选集中每个个体具有一个选择概率，这个概率取决于种群中个体的适应度及其分布。通常使用的选抨算法有：轮盘赌选择法、随机遍历抽样法、局部选择法、截断选择法和锦标赛选择法。(4)交义与变异机制在每一代种群中，以一定的交义概率尸c对染色体进行交叉，可以组合山继承父代有效模式的新个体，交义策略的选择对最终解的质量有很火影响。常用的交叉算法见表3．3。表3—3交叉算子类型名称特点单点交叉标准遗传算法成员双点交叉使用较多均匀交叉每一位以相IriJ的概率交叉多点交叉交叉点人干2部分匹配交叉何利于优良基Ⅲ片段的保留，常用于组合优化问题顺序交叉相对位置启发』℃交叉应用十知识领域交叉之后子代经历的变异，是通过对群体中个体的细微变动，维持群体的多样性。常川的变异算子』^!．表3-4。表3-4变异算子类型名称特点常规位变异标准遗传算法成员有效桀l大I变异避免，ff效堆【太1缺少自适应有效皋l大l，变异最低有效堆【大1个数自适应变化概率臼调整变异由两个串的相似性确定变异概率均匀变异由一个实数元崇以相同的概率在域内变动非均匀变异使整个矢量11：解窄问轻微变动针对不同的优化问题，需要反复实验米确定交义概率尸c和变异概率厶，这是一件繁琐的工作，而且很难找到适应丁每个问题的最佳值。在现有的求解VRP的遗传算法中，对交叉和变异概率通常的处理办法是：交叉概率只随机地选择一个较大的值，通常取0．25～0．75：而变异概率厶取一个较小的值，一般为O．01～0．2。(5)执行策略的改进遗传算法和其它的搜索方法相比，其优点是：由于遗传算法同有的并行性，使得它非常适合于人规模并行分布处理：此外，遗传算法易丁和其他技术结合，形成性能更优的问题求29 綦于GIS的智能酣送系统fiJf歹‘解方法。遗传算法也存在缺点：它在实际应用中容易产生早熟收敛的问题，即征进化群体中个体数少的适应函数值远大于其它个体，这样经过少数儿次迭代后，这些个体就-1，‘据了整个群体，进化过程就提前收敛了；而且在进化后_}}Ij搜索效率较低。为了提高遗传算法的执行效率和改进遗传算法的收敛性，可以把遗传算法和其它的优化算法相结合，使得优化行为可以得剑互补，并削弱参数选择的苛刻性。模拟退火(simulatedannealing)是～种基于热力学理论的优化方法，有着完善的全局收敛理论。在遗传算法中融入模拟退火思想，可以改善遗传算法早熟收敛的缺点，增强其全局收敛性。3．4．2．2模拟退火算法模拟退火算法是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程，它来源丁问体退火原理，模拟退火的基本思想为：(1)初始化：初始温度T(充分火)，初始解状态S(是算法迭代的起点)，每个r值的迭代次数￡；(2)对k=l，2，．．．，工产生新解F；(3)计算增量At'--f(S')-胸。其中脚为评价函数：(4)若At'