基于GIS物流配送线路优化与仿真

nbsp;   序
    现代商贸流通业是国民经济的重要支柱和先导产业。改革开
放以来，中国商贸流通业的发展有力地推动了国民经济的发展，
但其现代化、国际化程度还较低，过高的商贸流通成本和商务成
本正在严重制约中国产业国际竞争力的提升。
    当今世界，制造业与服务业的相互渗透和融合是一个明显的
经济发展趋向。现在，中国经济发展总体上处在工业化中期阶段，
沿海发达地区已开始进入工业化中后期阶段，制造业与服务业相
互融合或者说制造业服务化的趋势已经出现并将进一步增强。可
以预见，未来制造业国际竞争的主战场不在生产制造环节，而是
在研发设计、商贸流通和品牌经营等方面。谁占领了研发设计中
心、商贸流通中心的地位，谁就占据了产业链中高附加值环节，
拥有了产业发展的控制权。
    在过去的一二十年中，中国制造业主要依靠生产要素低价格优
势和生产规模优势，显示出较强的国际竞争力。但是，随着资源紧
张程度的加剧和生产要素价格上涨，环境压力的增大和保护成本的
上升，中国制造业发展正面临着严峻的新挑战。同时，随着经济全
球化和信息化进程不断加快，特别是在中国加入世界贸易组织后。
中国商贸流通领域的对外开放程度空前提高。跨国公司大举进入中
国零售、批发和物流等商贸流通领域，不仅深刻改变了中国商贸流
通业的发展格局和市场竞争秩序，而且直接影响着中国国民经济的
控制力和国家经济安全。因此，深化中国商贸流通业改革，推动商
贸流通领域的制度创新、技术创新和管理创新，推进中国商贸流通
业现代化和国际化进程，大幅度提高商贸流通效率，不仅对于提升
 中国商贸流通业的国际竞争力，而且对于创造中国制造业新的国际
竞争优势，都是紧迫而重大的研究课题和战略选择。
    令人遗憾的是，至今在中国经济生活中仍然严重存在着重生
产轻流通、重制造业轻服务业、重外贸轻内贸的传统习惯和思维
方式。在科学研究方面，有关商贸流通理论和重大现实问题研究
有分量的创新性成果不多，研究力量总体上比较薄弱。在学科建
设方面，虽然国际贸易学的理论体系和研究方法相对完善，但以
研究国内或区域内商品流通领域交易方式、交换关系及其规律为
主的贸易经济学，以前被商业经济学所取代，现在也没有形成与
国际主流经济学接轨、较为成熟的理论体系和研究方法。在人才
培养方面，中国严重缺乏零售、批发、外贸、物流等方面的高级
人才，高等学校虽然开设了市场营销、国际经济与贸易、电子商
务、物流管理等有关商贸流通专业，但这些专业横跨文科(如市
场营销专业属于管理学科、国际经济与贸易专业属于经济学科)
和工科(如电子商务专业和物流管理专业)，至今没有形成能满足
社会对复合型高级商贸流通人才需要和比较完整科学的贸易经济
学专业。由于缺乏现代商贸专业人才，中国本土商贸企业与跨国
公司在零售、批发和物流等领域的竞争中，明显处在弱势地位。
    2004年11月，浙江工商大学现代商贸研究中心被国家教育部
批准为部省共建人文社会科学重点研究基地，它肩负着在中国商
贸流通领域开展科学研究、人才培养、学术交流、资料信息建设
和提供咨询服务等重任。现代商贸研究中心现在下设有商贸业改
革与发展研究所、专业市场与流通研究所、商贸企业创新研究所
和国际贸易研究所，共有专兼职研究人员30多人。我们主要依托
现代商贸研究中心的力量，编辑出版“现代商贸研究丛书”，目的
就是为了“交流商贸研究信息，创新商贸研究理论”，努力为中国
商贸流通的理论研究、人才培养和实践创新尽一份绵薄力量。
    是为序。
 序
    在全国各地深入推进现代物流业发展、高等学校努力培养高
层次物流专业技术人才的时候，陈子侠教授的学术专著《基于
GIS物流配送线路优化与仿真》一书出版了，这是非常必要和及
时的，它为广大物流研究工作者，特别是从事商业流通型物流配
送中心、生产制造型物流配送中心从事末端送货线路优化工作的
科研人员和企业物流管理者，提供了一本重要的参考用书，同时
为高校物流专业高年级本科生、研究生提供了一本很好的参考
教材。
    物流作为一种社会经济运动的形态，自古至今已持续了上千
年，但未能受到人们的青睐，直到*近七、八年才在我国热了起
来。从20世纪90年代末开始，国家物资部门和贸易部门开始了
现代物流管理的推广与组织实施，以物流中心、配送中心等全新
的企业形态为标志，在我国流通业掀起了一场广泛的意义深远的
变革。2004年8月，国家发改委、商务部、公安部、铁道部、交
通部、海关总署、国家税务总局、中国民用航空总局、国家工商
行政管理总局等九部委联合下发了《关于促进我国现代物流业发
展的意见》，指出大力发展现代物流业，对于推动和提升相关产业
的发展，提高经济运行质量和效益，增强综合国力和企业竞争力
具有十分重要的意义，也把发展物流配送中心列为重点鼓励发展
的内容；2005年4月，由国家发改委牵头，建立了国家发改委、
商务部、铁道部、交通部、信息产业部、民航总局、公安部、财
政部、海关总署、工商总局、税务总局、质检总局、国家标准委、
中国物流与采购联合会、中国交通运输协会等15个单位共同参加
 的“全国现代物流工作部际联席会议制度”，强调切实加强对全国
现代物流工作的综合组织协调，充分发挥各部门的职能作用，促
进现代物流全面快速协调健康发展；2006年3月，在全国十届人
大四次会议通过的《国民经济和社会发展第十一个五年规划纲要》
第四篇“加快发展服务业”中，特别单列了一节“大力发展现代
物流业”，这在历史上从未有过，标志着现代物流作为产业的地位
在国家管理层面明确得到了确认。
    目前，我国物流需求主体仍以制造和商贸类的外资企业、新
兴企业为主，以高新技术、连锁经营和电子商务为代表的新兴企
业，对物流服务的及时性、准确性要求较高，正成为第三方物流
服务需求的重要来源，此外汽车、医药、通讯电子等行业物流需
求快速增长，物流需求已从运输、仓储等传统业务向物流控制管
理、配送等增值服务发展，部分企业开始要求全程物流服务。实
际上，近几年我国的社会物流基础设施能力和实力已逐步得到了
加强。据统计，2006年我国铁路营业里程达7．5万公里；公路里
程达192万公里，其中高速公路里程达4．1万公里；内河航道里
程达12．33万公里，全国港口泊位数达35108万个，其中深水泊
位(万吨级)944个，集装箱泊位155个。2006年，全国社会物
流总费用为38414亿元，按现价计算同比增长13．5％，增速比
2005年上升O．6个百分点，物流总费用与GDP的比率为18．3％，
从另一个侧面说明了我国物流管理的质量已经得到改善。改革开
放30多年来，我国国民经济总量成倍增长，进出口贸易总量居世
界第九位，这些数据的背后都是以巨大的物流量为支撑的。
    经过近十年的实践探索，我国已建成了一批融商流、物流、
信息流为一体，集储存保管、集散转运、流通加工、商品配送、
信息传递、代购代销、连带服务等多功能于一体的现代化物流配
送中心。我国的配送中心数量庞大，据相关机构统计，到2006年
底，国内大大小小物流配送中心数量已有5000多家。
    本书以物流配送中心末端配送问题为对象，以降低服务成本
和提高服务质量为目标，对其中具有普遍意义的配送网点划分和
单车线路问题进行了深入研究，对促进物流技术的研究与开发具
 有理论和实际应用价值。本书的创新性成果主要体现在：
    (1)提出了物流配送中心末端配送“广义工作量”和“送货
经济距离”的内涵，以配送线路广义工作量均衡和车辆容载量限
制为目标函数，建立系统模型，进行配送线路的划分。作者认为，
衡量一条线路的工作负荷，不能简单地以配送距离长短、送货量
或者网点数目多少这些单一指标作为衡量标准，而应将这些单一
指标通过加权计算，生成“广义工作量”予以综合衡量，本书给
出了工作量加权综合优化线路实现算法中各权系数的获取方法，
以此对不同线路的工作量负荷大小进行评价。送货经济距离是指
在一个配送网络中，送货车辆以行驶时间*短、行驶过程安全方
便为主要目标，从一个节点向另一个节点送货过程所形成的较短
实际距离。随着我国省际间、城际间、环市区等高速公路的不断
建设和逐步投入使用，越来越多的物流配送驾驶员在选择行驶路
线时，都以行驶时间*短、行驶过程安全方便作为目标出发点，
也就是说，驾驶员选择的路线一般不是理论上的空间*短距离，
而是综合考虑时间、行驶方便等多种因素后的较短距离!正是基
于这个考虑，本书作者提出了送货经济距离的概念。
    (2)根据工作量均衡原则，采用二阶*邻近算法求解线路划
分初始解，采用插入法对初始解进行改进，有效地提高了在多约
束条件下的算法有效性、正确性与合理性，把一个大规模的配送
网络、理论上复杂不可解的NP难点问题，转化为有限个实际上可
控、可观测的子系统进行求解。
    (3)单车线路优化过程中，采用同时兼顾单车线路网点数、
订货量和总经济距离的个体适应度函数的混合遗传算法用于单车
线路优化，降低了配送运行成本，同时根据配送线路道路拥挤度
的随机变化，确定网点间不同时间段的送货经济距离，及时调整
配送计划和配送路线。
    (4)上述研究成果与地理信息系统(GIs)相结合，已成功
应用于杭烟物流配送中心的配送网络，取得了明显的应用效果。
    当前，在发展现代物流的实践中，我国还面临认识、体制、
技术和人才等方面的制约，其中现代物流人才的缺乏，已严重影
 响了我国现代物流的发展，加快培养现代物流人才已成当务之急。
《基于GIs物流配送线路优化与仿真》是一本既具有理论性，又具
有实践性的物流类专业入门书籍。作者结合多年来从事物流学领
域的科研与教学，结合参加企业和政府物流研究项目的实践，较
为透彻完整地阐述了物流配送线路优化的基本理论和基本方法，
采用了大量的分析案例和图表，较为客观而真实地反映了物流配
送中心末端配送线路优化问题的理论研究和实际应用的前沿。相
信本书的出版，对国内物流配送理论和应用的研究，对国内高级
物流人才的培养，都将起到非常积极的促进作用。
    国务院学位委员会管理科学与工程学科评议组成员
    中国物流学会副会长
    上海物流研究院院长
    复旦大学现代物流管理研究中心主任、教授
 前言
    目前，物流配送中心的末端配送主要采取集中统一的送货方式，这种配
送模式必须综合考虑配送网点订货情况、物流配送中心规模、道路拥挤度、
道路整改等因素对配送效能的影响。本书从衡量配送线路实际工作量大小的
“广义工作量”指标入手，在地理信息系统(Geography Information System，
GIS)和企业网络数据库系统的支持下，以提高网点客户满意度和降低配送
成本为主要目标，进行物流配送中心末端配送线路优化课题的研究工作。
    研究工作主要包括配送线路广义工作量和送货经济距离概念的提出和应
用、配送线路的划分、单车线路优化和电子排单系统的可视化输出等内容。
    首先，本书提出了衡量配送线路工作量大小的“广义工作量”的概念。
广义工作量是配送中心进行配送线路区域、划分的一项重要经济指标，它与送
货经济距离(S)、送货量(D)、零售网点数量(N)等因素相关，它要求
不同配送线路之间广义工作量大小基本均衡，以使所有线路车辆送货员或驾
驶员在其配送过程中更好地为客户提供满意的服务。在体现广义工作量大小
的影响因素中，客户订货量(配送中心送货量)、送货经济距离、单车线路
的网点客户数等都是物流配送中心送货线路划分的重要因素。送货经济距离
是指在考虑路段长短、拥挤程度、车道数量、路面类型等因素基础上，实现
两点间配送时间*短的车辆行驶距离值。广义工作量概念的提出是进行配送
线路划分的先决条件，也是求解配送成本与网点客户服务水平之间均衡点的
前提。
    其次，在企业配送网络GIS支持下：以广义工作量均衡和车辆容载量为
目标值，对所有配送网点进行配送线路的划分，把一个包含几千个配送网点
的NP难点问题，转化为有限个实际可控、可观测的子系统进行求解。本书
采用*邻近算法求得物流配送中心送货线路划分的初始解，然后采用插入算
法对线路划分初始解进行改进，在GIS平台上的仿真结果表明了改进后线路
 划分方案的合理性。为了使划分结果进一步符合物流企业的实际应用，本书
在常规*邻近算法的基础上，提出了二阶*邻近算法的内涵，证明了该算法
每次选择下一个新网点时，其与当前线路上已有的两个次新网点所组成的网
点子集都是聚集度*高的，由此得到的配送线路中的客户网点聚集程度，要
高于常规一阶*邻近算法所得到的线路，这为下一阶段的单车线路优化提供
了较好的理论基础。
    本书在配送线路划分的前提下，在GIS平台上进行了单车配送线路的优
化调度，即综合考虑单车线路每次送货的网点数量、订货数量、道路拥挤度
等因素的变化，求解出每日每次每条送货线路的行驶路线安排，实现物流配
送中心送货车辆的每日每次动态电子排单的可视化输出。
    本书作者在对国内外单车线路优化问题大量调研的基础上，提出了自己
独特的、适合国内物流配送中心末端配送的单车线路求解方案：先用*节约
插值法构建问题的初始可行解，生成初始解路径集合；然后采用混合遗传算
法的全局搜索策略优化*节约插值法得到的初始解，进而得到一个相对满意
的解。由于传统遗传算法全局搜索能力很强但局部搜索能力不足，爬山算法
则具有很强的局部搜索能力，是一种常用的寻找局部*优解的方法，因此，
本书将二者相结合，以期取长补短。实践表明，这种策略可大大提高配送线
路的优化性能。为了使每日每次单车配送线路更加符合实际电子排单和道路
交通状况，本书以杭州市某段景区为例，从城市交通网络中道路路段间的地
理关联关系入手，在*短路径算法基础上考虑道路畅通度系数，探讨不同配
送时间段道路畅通度随机因素对单车线路配送效能的影响，分析结果使送货
经济距离数据库的建立和应用更加符合配送线路的实际运营状况。
    上述研究以杭州市区卷烟配送网络为数据获取源和应用案例，分别建立
物流配送中心配送线路划分和单车线路优化两个阶段的系统模型，采用多种
算法(或其混合)进行求解。由于大规模配送网络车辆路线问题是一个典
型的NP难点，随着网点数量的增加，系统计算的复杂度无论在空间上还是
在时间上都将成指数级增长，这对于规模较大的即时配送调度问题的优化计
算是难以接受的。据作者调研，物流配送企业对网点客户订单的有效反应要
求很高，节拍很短，有时甚至不允许电脑计算时间过长，因此有必要进行本
课题的系统建模与算法研究，解决物流配送中心末端配送的复杂配送网络求
解时间过长、计算工作量过高的现实问题。
    本书作者采用Maplnfo、VB、SQL Server 2000等开发技术将上述模型与
算法集成到企业配送网络GIS环境下，完成物流配送中心末端配送系统的设
计与实现。通过与GIS系统的集成，将线路划分结果与单车线路电子排单结
 果，直观地输出在电子地图上，从而实现物流配送中心末端配送车辆路线问
题的可视化输出控制。研究成果在烟草、百货、医药、油料等企业的物流配
送中心末端集中配送领域，具有普适性和推广应用前景。
    本书研究内容的创新点主要体现在以下几个方面：(1)在定义物流配
送中心送货线路“广义工作量”和“送货经济距离”概念的基础上，根据
不同配送线路工作量均衡和送货经济距离*短的多目标决策问题求解期望，
采用改进后的二阶*邻近算法和插入法进行送货线路划分，从而兼顾了配送
成本降低与客户满意度提高两者之间的“二律背反”关系；(2)单车线路
优化应用了标准遗传算法与爬山算法相结合的混合遗传算法，在其中的同化
操作中，首次提出并应用能综合体现单车线路网点数(N)、送货量(D)
和总经济距离(S)三个指标的个体适应度函数，作为判断单车线路同化操
作优劣的尺度标准；(3)根据道路拥挤度的随机变化，确定单车配送线路
任意两个网点间不同时间段的送货经济距离，及时调整配送计划和配送路
线，采用概率模型替代传统确定性模型；(4)研究成果已应用于杭烟物流
配送中心的配送网络，取得了明显的应用效果，弥补了国内车辆线路问题研
究大多停留在理论层次的不足。
    本书适合从事物流配送中心送货线路优化和配送车辆调度研究工作的专
业技术人员参考，同时适合作为高校物流专业高年级本科生、研究生的学习
参考用书，对物流配送企业、物流科研院所相关研究人员、管理人员和操作
人员，也具有较高的参考价值和实际应用价值。
    由于本人水平有限，时间仓促，书中不足之处在所难免，恳请各位专
家、读者批评指正。