物流配送中车辆优化调度问题的研究与实践.docx

物流配送中车辆优化调度问题的研究与实践.docx

《物流配送中车辆优化调度问题的研究与实践.docx》由会员分享，可在线阅读，更多相关《物流配送中车辆优化调度问题的研究与实践.docx（82页珍藏版）》请在冰点文库上搜索。

物流配送中车辆优化调度问题的研究与实践

沈阳航空工业学院

硕士学位论文

物流配送中车辆优化调度问题的研究与实践

姓名：

王鑫

申请学位级别：

硕士

专业：

计算机应用技术

指导教师：

孙小平

20060101

沈阳航空工业学院硕士学位论文

摘要

随着经济全球化和网络信息技术发展步伐的加快，现代物流作为一个新的经济增长点引起了全社会广泛的关注。

作为客户服务的直接手段，物流配送无疑是现代物流管理中的重要环节，配送线路的合理与否对配送速度、运营成本及经济效益影响很大。

采用科学合理的方法确定配送路线，是物流配送活动中非常重要的工作，对提高企业服务质量，增强企业的竞争力具有重要的意义。

车辆优化调度问题（ＶｅｈｉｃｌｅＳｃｈｅｄｕｌｉｎｇＰｒｏｂｌｅｍ，简称ＶＳＰ）是物流配送中的最为核心的内容，它是一个典型的ＮＰ难题，涉及到运筹学、应用数学，组合优化、图论与网络分析、计算机软件、计算机应用、物流科学、运输管理等众多学科领域。

ＶＳＰ是运筹学与组合优化领域的前沿与研究热点问题，对它的研究为组合优化理论与方法的发展有着积极的推动作用。

本文对国内外ＶＳＰ的研究成果进行了全面系统地分析，在已有数学模型的基础上，提出了适合制造企业实际需求的物流配送车辆调度问题模型的目标函数和约束条件，建立了有时限和无时限的纯装或纯卸的非满载车辆调度问题模型。

通过构造时间窗检查约束条件，求解有硬时间窗的ＶＳＰ。

在解决问题的过程中，对经典的ｃ．ｗ节约算法进行适当的修正，结合Ｄｉｊｋｓｔｒａ单源最短路径算法，不但求得满足实际需求的可行解，且分析了隐含点对最终线路的影响问题。

通过建立制造企业物流配送车辆调度系统，验证了上述算法在车辆路线管理上的可行性程有效性。

关键词：

物流配送；车辆优化调度闯题；纯装；纯卸；非满载；时间窗；Ｃ－Ｗ节约算法

沈阳航空工业学院硕士学位论文

Ａｂｓｔｒａｅｔ

Ａｌｏｎｇ、Ⅳｉｔ｝１ｔｈｅｅｃｏｎｏｍｉｃｇｌｏｂａｌｉｚａｔｉｏｎａｎｄｔｈｅｎｅｔｗｏｒｋｉｎｆｏｒｍａｔｉｏｎｔｅｃｈｎｉｑｕｅｓｔｅｐｐｉｎｇｕｐ，ｔｈｅｍｏｄｅｍｌｏｇｉｓｔｉｃｓｃａｔｃｈｅｓｔｈｅｗｈｏｌｅｓｏｃｉａｌａｔｔｅｎｔｉｏｎｅｘｔｅｎｓｉｖｅｌｙ

ａｓ

ａ

Ｄｅｗｅｃｏｎｏｍｙｇｒｏｗｔｈ

ｐｏｉｎｔ．Ｂｅｉｎｇｔｈｅｄｉｒｅｃｔｍｅａｎｓｏｆｔｈｅｃｕｓｔｏｍｅｒｓｅｒｖｉｃｅ，ｔｈｅｍｏｄｅｌｌｏｇｉｓｔｉｃｓｉｓｔｈｅｉｍｐｏｒｔａｎｔｔａｃｈｅｉｎｔｈｅｍｏｄｅｍｌｏｇｉｓｔｉｃｓｕｎｄｏｕｂｔｅｄｌｙ，ｗｈｅｔｈｅｒｔｈｅｄｉｓｔｒｉｂｕｔｉｏｎｒｏｕｔｅｉｓｒｅａｓｏｎａｂｌｅｉｔｈａｓｇｒｅａｔｉｎｆｌｕｅｎｃｅ

ｏｎ

ｏｒ

ｎｏｔ，ｖｅｒｙ

ｄｉｓｔｒｉｂｕｔｉｏｎｒａｔｅ，ｔｒａｎｓｐｏｒｔｃｏｓｔ

ａｎｄｅｃｏｎｏｍｉｃ

ｂｅｎｅｆｉｔ．Ｉｔｉｓ

ａ

ｉｍｐｏｒｔａｎｔｗｏｒｋｉｎｔｈｅｌｏｇｉｓｔｉｃｓｄｉｓｔｒｉｂｕｔｉｏｎａｃｔｉｖｉｔｙｔｏｃｏｎｓｔｉｔｕｔｅｔｈｅｄｉｓｔｒｉｂｕｔｉｏｎｓｃｉｅｎｔｉｆｉｃｑｕａｎｔｉｔｙｖｅｒｙ

ｃｏｒｅ

ｒｏｕｔｅ

ｂｙ

ａｎｄａｎｄ

ｒｅａｓｏｎａｂｌｅｍｅｔｈｏｄｓ．Ｉｔｉｓ

ｓｉｇｎｉｆｉｃａｎｔｍｅａｎｉｎｇｔｏｒａｉｓｅｔｈｅｅｎｔｅｒｐｒｉｓｅｓｅｒｖｉｃｅ

ｓｔｒｅｎｇｔｈｅｎｔｈｅｅｎｔｅｒｐｒｉｓｅｃｏｍｐｅｔｉｔｉｏｎ．Ｔｈｅｖｅｈｉｃｌｅｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｉｓｔｈｅ

ａ

ｏｆｔｈｅｃｏｎｔｅｎｔｉｎｔｈｅｌｏｇｉｓｔｉｃｓｓｃｏｐｅｓ，ｉｔｉｓｔｙｐｉｃａｌＮＰ－ｈａｒｄｐｒｏｂｌｅｍ，ｉｎｖｏｌｖｉｎｇｉｎ

ｍａｎｙ

ｒｅｓｅａｒｃｈ

ｓｕｂｊｅｃｔｓ

ｓｕｃｈ

ａｓ

ｏｐｅｒａｔｉｏｎｓｒｅｓｅａｒｃｈ，ａｐｐｌｉｅｄｍａｔｈｅｍａｔｉｃｓ，ｃｏｍｂｉｎａｔｏｒｉａｌ

ｏｐｔｉｍｉｚａｔｉｏｎ，ｎｅｔｗｏｒｋａｎａｌｙｓｉｓ，ｃｏｍｐｕｔｅｒｓｏｆｔｗａｒｅ，ｃｏｍｐｕｔｅｒａｐｐｌｉｃａｔｉｏｎｓ，ｌｏｇｉｓｔｉｃｓｓｃｉｅｎｃｅ，ｔｒａｎｓｐｏｒｔａｔｉｏｎｍａｎａｇｅｍｅｎｔ，ｅｔｃ．ＶＳＰｂｅｃｏｍｅｓｏｐｅｒａｔｉｏｎｓｒｅｓｅａｒｃｈａｎｄｃｏｍｂｉｎａｔｏｒｉａｌ

ａｄｖａｎｃｅｄ

ａｎｄｈｏｔｓｐｏｔｓｉｎｔｈｅｆｉｅｌｄｏｆ

ｏｐｔｉｍｉｚａｔｉｏｎ

ｒｅｓｅａｒｃｈ，ｒｅｓｅａｒｃｈｅｓｆｏｒＶＳＰ

ｃａｎｐｒｏｍｏｔｅ

ａｃｔｉｖｅｌｙｔｈｅｄｅｖｅｌｏｐｍｅｎｔｏｆｔｈｅｔｈｅｏｒｙａｎｄｍｅｔｈｏｄｏｆｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉｍｉｚａｔｉｏｎ．

ＴｈｅｒｅｓｅａｒｃｈｒｅｓｕｌｔｏｆｔｈｅｄｏｍｅｓｔｉｃａｎｄｉｎｔｅｒｎａｔｉｏｎａｌＶＳＰｉｓｃｏｍｐｌｅｔｅｌｙｉｎｔｈｉｓｐａｐｅｒ．Ｂａｓｅｄ

ｏｎ

ａｎａｌｙｉｓｅｄ

ｓｙｓｔｅｍａｔｉｃａｌｌｙ

ｔｈｅｍａｔｈｅｍａｔｉｃｓｍｏｄｅｌ，ｔｈｅｔａｒｇｅｔｆｕｎｃｔｉｏｎａｎｄｓｕｂｊｅｃｔ

ｃｏｎｄｉｔｉｏｎｆｏｒｌｏｇｉｓｔｉｃｓｖｅｈｉｃｌｅｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｍｏｄｅｌｉｓａｃｔｕａｌｒｅｑｕｅｓｔｏｆ

ｐｒｅｓｅｎｔｅｄ

ｏｒ

ｗｈｉｃｈａｄａｐｔ

ｔｏ

ｔｈｅ

ｍａｎｕｆａｃｔｕｒｉｎｇ．Ｔｈｅｎｏｎ—ｆｕｌｌｌｏａｄｅｄｐｕｒｅｐｉｃｋｕｐ

ｐｕｒｅｄｅｌｉｖｅｒｙｗｉｔｈｏｕｔ

ｔｉｍｅｗｉｎｄｏｗｓａｎｄｗｉｔｈｔｉｍｅｗｉｎｄｏｗｓｔｅｓｔｉｎｇ

ｗｉｎｄｏｗｓ

ＶＳＰｍｏｄｅｌｉｓｂｕｉｌｄｅｄ．Ｂｙｃｏｎｓｔｒｕｃｔｉｎｇｔｈｅｔｉｍｅ

ｓｕｂｊｅｃｔ

ｃｏｎｄｉｔｉｏｎ，ＶＳＰ

ｗｉｔｈ

ｈａｒｄｔｉｍｅｗｉｎｄｏｗｓｉｓｓｏｌｖｅｄ．Ｔｈｅｍｅｔｈｏｄ

ｔｈｅｗａｙｏｆ

ｅｘｔｅｎｄｓｔｈｅｄｏｍａｉｎｏｆａｐｐｌｉｃａｂｉｌｉｔｙｏｆｔｈｅｃｏｎｓｔｒａｉｎｔｓ

Ｃａｌｌ

Ｃ—Ｗｍｅｔｈｏｄ，ａｎｄ

ｈａｎｄｌｉｎｇ

ｔｈｅｔｉｍｅ

ｂｅｅｘｔｅｎｄｅｄｔｏｏｔｈｅｒｈｅｔａｉｓｔｉｃｓｏｆＴＳＥＩｔｉｓｅａｓｙｆｏｒｔｈｅａｌｇｏｄｔｈｒｎｔｏ

ｈａｎｄｌｅ

ｃｏｕｒｓｅ

ａｌｌｏｆｏｆｔｈｅ

ｋｉｎｄｓｏｆｃｏｎｓｔｒａｉｎｔｓａｎｄｉｓｐｒｏｖｉｄｅｄ

ｗｉｔｈ

ｂｅｔｔｅｒｉｎｔｅｒａｃｔｉｖｅｃｈａｒａｃｔｅｒｉｓｔｉｃ．Ｉｎｔｈｅ

ｃｏｎｓｔｒｕｃｔｉｎｇｔｈｅｒｏｕｔｅ，ｔｈｅｒｅｄｕｐｌｉｃａｔｅｄｅｌｉｖｅｒｙｔｏｄｏｍｉｃｉｌｅｉｓｅｌｉｍｉｎａｔｅｄ．Ｉｎｔｈｅｓｏｌｖｉｎｇｐｒｏｂｌｅｍ，ｔｈｅ

ｃｏｕｒｓｅ

Ｃ—Ｗ

ｓａｖｉｎｇｍｅｔｈｏｄｓｉｓｍｏｄｉｆｉｅｄｐｒｏｐｅｒｌｙａｎｄｃｏｍｂｉｎｅｓ

ｗｉｔｈ

ＩＩ

沈阳航空工业学院硕士学位论文

ｓｉｎｇｌｅ—ｓｏｕｒｃｅｓｈｏｒｔｅｓｔｐａｔｈａｌｇｏｒｉｔｈｍ，ｗｈｉｃｈｎｏｔｏｎｌｙｔｈｅｆｅａｓｉｂｌｅｒｅｓｕｌｔｆｏｒｔｈｅａｃｔｕａｌ

ＯｉｌＤｉｊｋｓｔｒａｒｅｑｕｅｓｔｓｉｓａｃｃｅｐｔｅｄ，ｂｕｔｔｈｅｑｕｅｓｔｉｏｎｔｈａｔｔｈｅｃｏｎｎｏｔａｔｉｖｅｐｏｉｎｔａｆｆｅｃｔｓ

ａｎａｌｙｓｉｅｄ．Ｂｙｂｕｉｌｄｉｎｇｔｈｅｌｏｇｉｓｔｉｃｓｖｅｈｉｖｌｅｓｃｈｅｄｕｌｉｎｇｓｙｓｔｅｍｔｈｅｆｉｎａｌｐａｔｈｉｓｆｏｒｍａｎｕｆａｃｔｕｒｉｎｇ，ｔｈｅｆｅａｓｉｂｉｌｉｔｙａｎｄｆｅａｓｉｂｉｌｉｔｙｏｆｔｈｅａｂｏｖｅａｌｇｏｒｉｔｈｍｉｓｖｅｒｉｆｉｅｄ．

Ｋｅｙｗｏｒｄｓ：

ＬｏｇｉｓｔｉｃｓＤｉｓｔｒｕｂｕｔｉｏｎ；ＶｅｈｉｃｌｅＳｃｈｅｄｕｌｉｎｇ

Ｄｅｌｉｖｅｒｙ；Ｎｏｎ－ｆｕｌｌＬｏａｄｅｄ；ＴｉｍｅＰｒｏｂｌｅｍ；ＰｕｒｅＰｉｃｋｕｐ；ＰｕｒｅＳａｖｉｎｇｓＷｉｎｄｏｗｓ；Ｃ－ＷＭｅｔｈｏｄｓ１１１

原创性声明

本人郑重声明：

所呈交的学位论文是本人在导师的指导下独立完成的。

除文中已经注明引用的内容外，本论文不包含其他个人或集体已经发表或撰写过的作品或成果，也不包含本人为获得其他学位而使用过的成果。

对本文研究做出重要贡献的个人或集体均已在论文中进行了说明并表示谢意。

本声明的法律后果由本人承担。

论文作者签名：

王鼎Ⅻ缉１月９日

版权授权说明

本人授权学校“有权保留送交学位论文的原件，允许学位论文被查阅和借阅，学校可以公布学位论文的全部或部分内容，可以影印、缩印或其他复制手段保存学位论文”；愿意将本人学位论文电子版提交给研究生部指定授权单位收录和使用。

学校必须严格按照授权对论文进行处理，不得超越授权对毕业论文进行任意处置。

授权人：

王霹扣‘年ｆ月旁日

沈阳航空工业学院硕士学位论文

第１章绪论

１．１引言

当前，现代物流已被公认为是企业在降低物质消耗、提高劳动生产率以外创造利润的第三个重要源泉，也是企业降低生产经营成本，提高产品市场竞争力的重要途径１１埘。

据专家测算，现代物流成本约占企业经营成本的３０—５０％，当一个有效的物流系统与企业主要商业系统集成之后，可使仓储量降低５０％，准时交货率提高４０％，营业收入增加１０％以上【２，”。

在经济发达国家和一些经济水平较高的发展中国家，现代物流水平己成为影响企业竞争力的关键因素ｍｌ。

与发达国家相比，我国的物流产业效率较低【２】。

根据全国第三产业普查资料，我国交通运输、仓储、代理和批发等行业的成本费用之和占国民生产总值的比重为１５％左右，如果考虑其它相关流通环节的费用和流通过程中的物流损失，则全社会物流费用支出约占国民生产总值的２０％以上，而美国的全社会物流费用支出仅占其国民生产总值的１０％左右。

另据有关资料，目前我国一般工业品从产品出厂经过装卸、储存、运输等各个物流环节到消费者手中的流通费用约占商品价格的５０％左右；而新鲜水果、易变质食品、某些化工产品的流通费用有的高达商品售价的７０—８０％；我国汽车零配件的生产中，其加工装配时间仅占２％，而９８％的时间是原材料、零配件的储存、装卸和搬运时间。

在各种产品的生产和流通环节中还有大量原材料、零部件和产品的“库存”［５１。

这些费用和时间上的消耗以及大量存在的库存正是潜在的实施物流管理的领域，为物流的发展留下了巨大的空间。

在这种形势下，研究如何通过实施科学的物流管理，以提高物流效率、降低物流成本、提高服务质量是十分必要的。

物流配送是现代化物流中的一个重要环节【２．６１，它是指按客户（包括零售商、用户等）的订货要求（包括货物种类、数量和时间等方面的要求），在物流中心（也称物流基地、物流据点，包括配送中心、仓库、车站、港口等）进行分货、配货工作，并将配好的货物及时送交收货人的物流活动。

物流配送过程主要包括以下作业环节：

从生产工厂进货或运达并集结的集货作业：

根据各个客户的不同需求，在物流中心将所需要的货物挑选出来的分货和配货作业；考虑配送货物的重量和体积，充分利用车辆的载重和容积的货

沈阳航空工业学院硕士学位论文

物配装作业；合理确定车辆配送路线并及时送货的作业。

可见，物流配送是一种集集货、分货、配货、配装、送货等多种功能为一体的物资流通方式。

在物流配送业务中【２］’存在许多优化决策的问题，车辆优化调度问题涉及面较广，需要考虑的因素较多，本文将着重研究物流配送车辆调度问题，该问题包括集货线路优化，货物配装及送货线路优化等，是物流配送系统优化的关键。

国外将物流配送车辆调度问题归结为Ⅵ冲（Ｖｅｈｉｃｌｅ

Ｓｃｈｅｄｕ／ｉｎｇＲｏｕｔｉｎｇＰｒｏｂｌｅｍ，即车辆路径问题）和ＶＳＰｆＶｅｈｉｃｌｅＰｒｏｂｌｅｍ，即车辆调度问题），该问题于１９５９年由Ｄａｎｔｚｉｇ和Ｒａｉｍ＿ｓｅｒ提出后ｌ”，很快便引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家以及运输计划制定者的极大重视，并一直是运筹学与组合优化领域的前沿与热点问题。

ＶＲＰ与ＶＳＰ是根据问题的空间特性和时问特性的相对重要性来划分的１８］，一般认为，当不考虑时间要求，仅根据空间位置安排线路的称为Ｒｏｕｔｉｎｇ，根据时间要求安排线路的称为Ｓｃｈｅｄｕｌｉｎｇ，同时考虑空间位置和时间要求的称为Ｒｏｕｔｉｎｇ和Ｓｃｈｅｄｕｌｉｎｇ混合问题，也有不区分两者的，若有具体约束则加上定语，例如将有时间要求的车辆调度问题称为ＶｅｈｉｃｌｅＲｏｕｔｉｎｇＰｒｏｂｌｅｍｗｉｔｈＴｉｍｅＷｉｎｄｏｗｓ。

在现实应用中，由于Ｓｃｈｅｄｕｌｉｎｇ涉及的内容和关键技术比Ｒｏｕｔｉｎｇ宽泛，因此绝大多数研究者的主要研究兴趣集中在Ｓｃｈｅｄｕｌｉｎｇ问题上，且主要对车辆调度问题（Ｖｅｈｉｃｌｅ

简称ＶＳＰ）开展广泛的研究。

在现实生产和生活中１２】，邮政投递问题、飞机、铁路车辆、水运船舶及公共汽车的调度问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题都可以抽象为物流配送车辆调度问题。

因此，将物流配送车辆调度问题作为研究对象具有一定的理论和现实意义。

ＳｃｈｅｄｕｌｉｎｇＰｒｏｂｌｅｍ，

１．２ＶＳＰ概述

ＶＳＰ描述ｌ－２．１

物流配送车辆调度问题可以描述为【９】：

在一个存在供求关系的系统中，有若干台车辆、若干个物流中心和客户，要求合理安排车辆的行车路线和出行时间，从而在给定的约束条件下（如货物需求量、发送量、交发货时间、车辆容量限制、行驶罩程限制、时间限制等），把客户需求的货物从物流中心送到客户，把客户供应的货物从客户取到物２

沈阳航空工业学院硕士学位论文

流中心，并使目标函数（如路程最短、费用最少，时间尽量小、利润最大、使用车辆数尽量少等）取得优化。

Ｏｒｌｏｆｆ在１９７４年提出了物流配送车辆调度问题的～般网络模型叙述如下ｌｌｏ］：

设Ｇ＝（Ｖ，Ｅ，Ａ）是一个连通的混合网络，Ｖ是顶点集（表示物流中心、客户、停车场等），Ｅ、Ａ分别为无向的边集和有向的弧集，Ｅ中的边和Ａ中的弧均被赋权（可以表示配送的距离、时间或费用）。

Ｖ’、Ｅｆ、Ａ１分别为Ｖ、Ｅ、Ａ的子集，求满足约束条件（包括客户的货物需求或供应量约束、需求或供应时间约束、配送车辆一次配送的最大行驶距离约束、车辆的最大载重量约束等），并包含Ｖ‘、Ｆ、～的一些巡回路线，使目标函数取得优化，目标函数可以取配送总里程最短、配送总费用最低、配送总时间最少、使用的配送车数最少，配送车辆的满载率最高等。

１．２．２ＶＳＰ构成要素

物流配送车辆调度问题主要包括货物、车辆、物流中心、客户、运输网络、约束条件和目标函数等要素［２】ｏ

（１）货物。

货物是配送的对象。

可将每个客户需求（或供应）的货物看成一批货物。

每批货物都包括品名、包装、重量、体积、要求送到（或取走）的时间和地点、能否分批配送等属性。

货物的品名和包装，是选用配送车辆的类型以及决定该批货物能否与其它货物装在同一车辆内的依据。

例如，一些货物因性质特殊需要使用专用车辆装运；～些货物因性质特殊不能与其它货物装在同一车辆内；一些货物虽然性质特殊，但由于包装条件很好，故也能与其它货物装在同一车辆内。

货物的重量和体积是进行车辆装载决策的依据。

当某个客户需求（或供应）货物的重量或体积超过配送车辆的最大装载重量或容积时，则该客户将需要多台车辆进行配送。

货物的送到（或取走）时间和地点是制定车辆的出行时间和配送路线的依据。

允许货物分批配送，是指某个客户的需求（或供应）的货物可以用多辆车分批送到（或取走），即使其需求（或供应）量在一辆车的装载量以下。

（２）车辆。

车辆是货物的运载工具。

其主要属性包括车辆的类型、装载量，一次配３

沈阳航空工业学院硕士学位论文

送的最大行驶距离、配送前的停放位置及完成任务后的停放位置等。

车辆的类型有通用车辆和专用车辆之分，通用车辆适于装运大多数普通货物，专用车辆适于装运～些性质特殊的货物。

车辆的装载量是指车辆的最大装载重量和最大装载容积，是进行车辆装载决策的依据。

在某配送系统中，车辆的装载量可以相同，也可以不同。

对每台车辆一次配送的行驶距离的要求可分为以下几种情况：

①无距离限制；

②有距离限制；

③有距离限制，但可以不遵守，只是不遵守对需另付加班费。

车辆在配送前的停放位置可以在某个停车场、物流中心或客户所在地。

车辆完成配送任务后，对其停放位置的要求可分为以下几种情况：

①必须返回出发点：

②必须返回某停车场；

③可返回到任意停车场；

④可停放在任何停车场、物流中心或客户所在地。

（３）物流中心。

也称为物流基地、物流据点，是指进行集货、分货、配货、配装、送货作业的配送中心、仓库、车站、港口等。

在某配送系统中，物流中心的数薰可以只有一个，也可以有一个以上；物流中一心的位置可以是确定的，也可以是不确定的。

对于某个物流中心，其供应的货物可能有一种，也可能有多种，其供应的货物数量可能能够满足全部客户的需求，也可能仅能满足部分客户的需求。

（４）客户。

也称为用户，包括分仓库、零售商等。

客户的属性包括需求（或供应）货物的数量、需求（或供应）货物的时间、需求（或供应）货物的次数及需求（供应）货物的满足程度等。

在某个配送系统中，某个客户的需求（或供应）货物的数量可能大于车辆的最大装载量，也可能小于车辆的最大装载量；而该系统全部客户的货物需求（或供应）总量可能超过全部车辆的总装载量，也可能低于全部车辆的总装载量。

某客户的需求（或供应）货物的时间，是指要求货物送到（或取走）的时间，对配４

沈阳航空工业学院硕士学位论文

送时间的要求可分为以下几种情况：

①无时间限制；

②要求在指定的时间区间（也称为时间窗）内完成运输任务；

⑨有时间限制，但可以不遵守，只是不遵守时要给予一定的惩罚。

某客户的需求＜或供应）货物的次数可能仅有一次，即只需一次配送服务；也可能为多次，即需要多次配送服务。

某客户对需求（或供应）货物的满足程度的要求可分为两种情况：

①要求全部满足；

②可以部分满足，但不满足时要受到惩罚。

（５）运输网络。

运输网络是由顶点（指物流中心、客户、停车场）、无向边和有向弧组成的。

边、弧的属性包括方向、权值和交通流量限制等。

某运输网络中可能仅有无向边；也可能仅有有向弧；还可能既有无向边，又有有向弧。

运输网络中边或弧的权值可以表示距离、时间或费用。

边或弧的权值变化分为以下几种情况：

①固定，即不随时间和车辆的不同而变化；

⑦随时间不同而变化：

③随车辆的不同而变化；

④既随时间不同而变化，又随车辆不同而变化。

对运输网络权值间的关系可以要求其满足三角不等式，即两边之和大于第三边，也可以不加限制。

对运输网络中顶点、边或弧的交通流量要求分为以下几种情况：

①无流量限制；

②边、弧限制，即每条边、弧上同时行驶的车辆数有限；

③顶点限制，即每个顶点上同时装、卸货的车辆数有限；

④边、弧、顶点都有限制。

（６）约束条件。

物流配送车辆调度问题应满足的约束条件主要包括：

①满足所有客户对货物品种、规格、数量的要求。

②满足客户对货物发到时间范围的要求。

５

沈阳航空工业学院硕士学位论文

⑧在允许通行的时间进行配送（如有时规定白天不能通行货车等）。

④车辆在配送过程中的实际载货量不得超过车辆的最大允许装载量，在物流中心现有运力范围内。

（７）目标函数。

对物流配送车辆调度问题，可以只选用一个目标，也可以选用多个目标。

经常选用的目标函数主要有：

①配送总里程最短。

配送里程与配送车辆的耗油量、磨损程度以及司机疲劳程度等直接相关，它直接决定运输的成本，对配送业务的经济效益有很大影响。

由于配送罩程计算简便，它是确定配送路线时用得最多的指标。

⑦综合费用最低。

降低综合费用是实现配送业务经济效益的基本要求。

在物流配送中，与取送货有关的费用包括：

车辆维护和行驶费用、车队管理费用、货物装卸费用、有关人员工资费用等。

③准时性最高。

由于客户对交货时间有较严格的要求，为提高配送服务质量，有时需要将准时性最高作为确定配送路线的目标。

④运力利用最合理。

该目标要求使用较少的车辆完成配送任务，并使车辆的满载率最高，以充分利用车辆的装载能力。

⑤劳动消耗最低。

即以司机人数最少、司机工作时间最短为目标。

１．２．３ＶＳＰ分类

自ＶＳＰ被提出后，Ｂｏｄｉｎ和Ｇｏｌｄｅｎ（１９８３）１８１等许多学者对ＶＳＰ从不同角度，按不同的标准进行了多种分类。

（１）按物流中心的数目分，有单物流中心问题（配送系统中仅有一个物流中心）和多物流中心问题（配送系统中存在多个物流中心）。

（２）按车辆载货状况分，有满载问题（由于客户需求或供应的货物数量大于或等于车辆的载重量，故完成一项配送任务需要一辆及其以上的配送车辆，配送车辆需要满载运行）、非满载问题（由于客户需求或供应的货物数量小于车辆载重量，多项配送任务可共用一辆配送车辆，车辆在配送过程中经常处于不满载状态）以及满载和非满载混合问题（由于一部分客户需求或供应的货物数量大于或等于车辆的载重量，而另一部分客户需求或供应的货物数量小于车辆的载重量，造成一些配送车辆需要满载运行，而另一６

沈阳航空工业学院硕士学位论文

些车辆则经常处于不满载状态）。

（３）按配送任务特征分，有纯送货问题（仅考虑从物流中心向客户送货，也称为纯卸问题）或纯取货问题（仅考虑把各客户供应的货物取到物流中心，也称为纯装问题）及取送混合问题（既考虑将客户需求的货物从物流中心送到各个客户，同时考虑将客户供应的货物从客户取到物流中心，也称为装卸混合问题或集货和送货一体化问题）。

（４）按客户对货物取（送）时间的要求分，有无时限问题（客户对货物的取走或送到的时间无具体要求）和有时限问题（客户要求将需求的货物在规定的时间窗内送到，将供应的货物在规定的时间窗内取走，也称为有时间窗问题）。

有时限问题又可以分为硬时间窗问题（客户要求货物必须在规定的时间窗内送到或取走，不能提前也不能拖后）和软时间窗问题（客户要求将货物尽量在规定的时间窗内送到或取走，但也可以提前或拖后，只不过在提前或拖后时，要对配送企业实施一定的惩罚）。

（５）按车辆类型数分，有单车型问题（所有配送车辆的载重量相同）和多车型问题（配送车辆的载重量不完全相同）。

（６）按车辆对车场的所属关系分，有车辆开放问题（即车辆完成配送任务后可以不返回其发出车场）和车辆封闭问题（车辆完成配送任务后必须返回其发出车场）。

（７）按优化目标数分，有单目标问题（仅考虑一个配送目标）和多目标问题（同时考虑多个配送目标）。

１．２．４本文研究内容的界定

现实中的物流配送车辆调度问题是十分复杂的，为了方便建模和求解，需要对现实问题进行一些抽象和简化。

现对本文研究的物流配送车辆优化调度问题做如下界定：

（１）从一个物流中心向多个客户送货或取货，物流中心和客户的位置一定，物流中心供应的货物，能够满足所有客户的需求。

（２）各个客户需求的或供应的货物均可以相互混装，即可以装在同一配送车辆内，每个客户的货物需求量或供应量不超过配送车辆的最大载重量，每个客户的送货或取货要求必须满足，且仅能由一台车辆完成，不允许分批配送或取走。

（３）每台配送车辆的最大载重量一定，不允许超载：

配送或取货时，设每台车辆都从物流中心出发，向～些客户提供配送或取货服务后，最终返回物流中心。

７

沈阳航空工业学院硕士学位论文

（４）对于客户要求将需求货物送到或取走的时间，分别考虑以下两种情况：

①无时间限制；

②要求在指定的时间窗内完成送货或取货任务，不允许提前或拖后，即硬时间窗：

（５）物流中心与客户之间以及客户相互之间的距离己知，配送车辆在物流中心、客户间的行使时间已知，不考虑运输网络中车辆流量的限制。

根据以上界定，本文所研究的物流配送车辆优化调度问题均属于单物流中心、非满载且车辆封闭的车辆调度问题。

１．３ＶＳＰ求解方法综述

１．３．１国内外研究动态和水平

国外对物流配送车辆调度问题作了大量而深入的研究。

早在１９８３年，Ｂｏｄｉｎ、Ｇｏｌｄｅｎ等人在他们的综述文章中就列举了７００余篇有关文献【８ｌ，对该领域的研究成果进行了详尽的阐述。

Ｃｌ