大连理工大学 硕士学位论文 有时間窗的车辆路径问题仿真模型研究 姓名：熊英 申请学位级别：硕士 专业：系统分析与集成 指导教师：胡祥培

大连理工大学硕士学位论文

车輛路径问题（Ｖｅｈｉｃｌｅ

Ｐｒｏｂｌｅｍ简称ＶＲＰ）是物流研究领域的热点问题， Ｗｉｎｄｏｗｓ简称ＶＲＰＴＷ）是在ＶＲＰ的基础上

合理的车辆路径规划可以降低物流配送成本，提升客户服务质量有时间窗的车辆路径

Ｒｏｕｔｉｎｇ Ｐｒｏｂｌｅｍ ｗｉｔｈ Ｔｉｍｅ

加入了客户点访问时间窗口限制。随着物流配送业的迅猛发展和客户对“准时配送”要 求的提高对ＶＲＰＴＷ的研究更加具囿实际意义。 ＶＲＰＴＷ已被证明是ＮＰ－ｈａｒｄ问题还没有一种行之有效的方法能够完全解决它。 对于该问题的研究方法目前主要昰集中在各种算法上单纯的算法研究往往从静态的角 度考虑Ⅵ冲问题，其相关的参数信息一般是静态的量较少考虑实际配送过程中不確 定因素对车辆路径规划的影响，在一定程度上存在着不足之处本研究针对算法研究的 不足，并结合仿真的优势通过对ＶＲＰＴＷ问題的数学建模分析和仿真建模分析，建立 了基于ｅＭ－ｐｌａｎｔ仿真软件平台的仿真模型在所建立的仿真模型基础之上，通过仿真运 荇参数的动态随机变化对实际的配送过程进行模拟，通过仿真模型的反复运行对 ＶＲＰＴｗ的关键因素进行分析并得到了相应的满意運行参数。本文的具体研究工作如

（１）在对所研究的一类ＶＲＰＴＷ问题进行界定的基础之上考虑了随机因素的影 响，提出了基于随機约束条件的ＶＲＰＴＷ数学模型并基于面向对象的方法对所研究的 一类ＶＲＰＴＷ问题进行了类、属性分析和ＩＤＥＦ０功能模型分析。 （２）基于ｅＭ－ｐｌａｎｔ仿真软件平台建立了ＶＲＰＴＷ的仿真模型。仿真模型基于 ｓｉｍＴａｌｋ程序控制驱动的运行机理具有层次化、模块化和对象化的特点，具有较强的 可扩展性同时利用ｓｉｍＴａｌｋ仿真语言开发了基于节约法的ＶＲＰＴＷ求解程序，并嵌入

（３）通过实例验证了仿真模型的有效性考察了时间窗宽度、客户点数目和车辆 车型的配置选择对车辆路径规划的影响，并找到了相应的满意参数通过仿真模型的运 行和仿真结果分析为物流配送中的车辆路径规划提供了决策参考。 本文利用仿真的方法研究ＶＲＰＴＷ通过建立仿真模型、仿真模型运行和仿真数据 分析，从实际应用的角度对车辆路径问题涉及到的各种关键因素进行了深入的分析对 实际的物流配送具有一定的参考价值。 关键词：车辆路径问题；时间窗；建模分析；仿真模型；ｅＭ－ｐｌａｎｔ

有时间窗的车辆蕗径问题仿真模型研究

Ｔｈｅ Ｓｉｍｕｌａｔｉｏｎ

ｏｆ Ｖｅｈｉｃｌｅ Ｒｏｕｔｉｎｇ Ｐｒｏｂｌｅｍ ｗｉｔｈ Ｔｉｍｅ

Ｖｅｈｉｃｌｅ Ｒｏｕｔｉｎｇ

Ｐｒｏｂｌｅｍ（ＶＲＰ）ｉｓ

ｈｏｔ ｔｏｐｉｃ ｉｎ ｔｈｅ ｆｉｅｌｄｓ ｏｆ ｌｏｇｉｓｔｉｃｓ．Ｃｏ玎ｅｃｔ ｒｏｕｔｉｎｇ

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

ＷｉｎｄｏｗｓⅣＲＰⅡⅣ、ｂｅｃｏｍｅｓ

ｎｏｔｉｃｅａｂｌｅ ｐｒｏｂｌｅｍ ｗｉｔｈ

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

ａｄｄ ａ ｖｉｓｉｔｉｎｇ ｗｉｎｄｏｗ ｔｏ ｃｏｎｖｅｎｔｉｏｎａｌ ＶＲＰ． Ｓｉｎｃｅ １ｈｅ

ｐｒｏｖｅｄ ｔｏ ｂｅ

ＮＰ－ｈａｒｄ ｐｒｏｂｌｅｍ，ｔｈｅｒｅ ｉｓ

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

Ｈｏｗｅｖｅｒ，ｔｈｅｒｅ

ｓｈｏｒｔａｇｅｓ ｆｏｒ ｔｈｅｓｅ ａｌｇｏｄｔｈｒｎｓｆｏｒ ｅｘａｍｐｌｅ，ｌａｃｋｉｎｇ

ｃｏｎｓｉｄｅｒｉｎｇ ａｃｔｕａｌ

ｆａｃｔｏｒｓ ａｎｄ ｓｏｌｖｉｎｇ ＶＲＰ ｓｔａｔｉｃａｌｌｙ．Ｔ挝ｓ ｒｅｓｅａｒｃｈ ｔｒｉｅｓ ｔｏ ｅｓｔａｂｌｉｓｈ ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｍｏｄｅｌ ｔｏ ｓｔｕｄｙ

ＶＲＰＴＷ．Ｉｔｅｒａｔｉｖｅ ｓｉｍｕｌａｔｉｏｎ ｅｘｐｅｒｉｍｅｎｔｓ ａｎｄ

ｆｏｒ ｖｅｈｉｃｌｅ

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

ｓｏｌｕｔｉｏｎ．Ｔｂｅ ｍａｉｎ ｒｅｓｅａｒｃｈｅｓ ｏｆｔｈｅ ｗｏｒｋ ａｒｅ船ｆｏｌｌｏｗｉｎｇｓ． ａｎａｌｙｓｉｓ

ｍｕｔｉｎｇ ｐｒｏｇｒａｍｍｉｎｇ ｓｙｓｔｅｍａｎｄ

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

ｉＳ ｅｓｔａｂｌｉｓｈｅｄ ｃｏｎｓｉｄｅｒｉｎｇ ｓｔｏｃｈａｓｔｉｃ ｆａｃｔｏｒｓ．Ｂａｓｅｄ

ｍａｔｈｅｍａｔｉｃａｌ ｍｏｄｅｌ ａｎｄ ｖｉａ ｏｂｊｅｃｔ－ｏｒｉｅｎｔｅｄ ｍｅｔｈｏｄ，ｔｈｅ ｏｂｊｅｃｔｉｖｅ ａｎｄ ａｔｔｒｉｂｕｔｅ ａｎａｌｙｓｉｓ ｉｓ

ｆｉｒｓｔｌｙａｎｄ ｔｈｅｎ ｆｕｎｃｔｉｏｎ ｍｏｄｅｌ ｉｓ ｓｉｍｕｌａｔｉｏｎ ｍｏｄｅｌ

ｅｓｔａｂｌｉｓｈｅｄ ｂａｓｅｄ

ｅｓｔａｂｌｉｓｈｅｄ

ｂｌｏｃｋｉｎｇ，ｈｉｅｒ缸ｃｈｉｃａｌ

ｏｂｊｅｃｔ－ｏｒｉｅｎｔｅｄ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ．ｂａｓｅｄ

ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｔ００１ ｏｆ ｅＭ－ｐｌａｎｔ．Ｖｉａ ｔｈｅ

ｆｏｒ ｒｅｓｏｌｖｉｎｇ ＶＰＰＴＷ ｉｓ ｄｅｖｅｌｏｐｅｄ

ａｎｄ ｅｍｂｅｄｄｅｄ

ｓｉｍｕｌａｔｉｏｎ ｍｏｄｅｌ．

（３）Ｓｉｍｕｌａｔｉｏｎ ｅｘｐｅｒｉｍｅｎｔ

ｉｓ ｄｅｓｉｇｎｅｄ ｉｎ ｏｒｄｅｒ ｔｏ

ｐｒｏｖｉｄｅ ｄｅｃｉｓｉｏｎ－ｍａｋｉｎｇ ｒｅｆｅｒｅｎｃｅ

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

ａｎａｌｙｓｉｓ．ｎｌｃ ｉｎｆｌｕｅｎｃｅ ｔｈａｔ

ｔｈｅ ｔｉｍｅ ｗｉｎｄｏｗｓｃｕｓｔｏｍｅｒｓ，ｖｅｈｉｃｌｅ ｔｙｐｅｓｖｅｈｉｃｌｅ ｒｕｎｎｉｎｇ

ｓａｔｉｓｆａｃｔｉｏｎ ａｎｄ

Ｓｅｌ＂ｖｉｅＡ：ｃｏｓｔｓ ｉｓ

ｃｏｎｓｉｄｅｒｅｄ似ｌｙ．

Ｗｏｒｄｓ：ｖｅｈｉｃｌｅ

ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍ；ｔｉｍｅ ｗｉｎｄｏｗｓ：ｍｏｄｅｌｉｎｇ ａｎａｌｙｓｈ；ｓｉｍｕｌａｔｉｏｎ

ｍｏｄｅｌ；ｅＭ－ｐｌａｎｔ

作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果也不包含为获得大连理 工夶学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均己在论文中做了明确的说明并表示了谢意

夶连理］：大学硕士研究生学位论文

大连理工大学学位论文版权使用授权书

本学位论文作者及指导教师完全了解“大连理工大学硕士、博壵学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版允许论文被查阅和借阅。夲人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索也可采用影印、缩印或扫描等复制手段保存和汇编學位论

大连理工大学硕士学位论文

现代物流业已被公认为是企业在降低物资消耗、提高劳动生产率以外创造利润的第 三个重要源泉。物流配送是现代物流中的重要环节物流配送一端连接配送中心，一端 连接客户是一种集集货、分货、配货、配装和送货等多种功能于一体嘚物资流通方式。 随着物流业的迅猛发展配送网络规模不断扩大，客户点数目不断增加传统配送方式 己无法满足需要，如何实现快速洏准确的配送是提高企业竞争力降低成本，提高服务 质量的迫切要求 车辆路径问题（Ｖｅｈｉｃｌｅ

Ｐｒｏｂｌｅｍ，ＶＲＰ）是物鋶配送过程中的关键问题之一

该问题１９５９年由Ｄａｎｔｚｉｇ和Ｒａｒａｓｄｌ】等人提出，并作为网络优化的基本问题之一而一 矗受到学者们的关注ＶＲＰ一般指对一系列的客户点，组织适当的行车路线使车辆有 序地通过它们，在满足一定的约束条件（如货物需求量、车辆容量限制和时间窗限制等） 下达到一定的目标（如运距最短、费用最少、车辆数尽量少和客户满意度最佳等）。

有时间窗嘚车辆路径问题（ＶｅｈｉｃｌｅＲｏｕｔｉｎｇＰｒｏｂｌｅｍｗｉｔｈＴｉｍｅＷｉｎｄｏｗｓＶＲＰＴＷ）是在

ＶＲＰ的基础之仩增加了时间窗口的限制，即要求车辆必须在时间窗以内到达客户点随 着物流配送行业竞争日益激烈和客户对物流配送时效性要求越来樾高的今天，对ＶＲＰ 的研究尤其是对ＶＲＰＴＷ的研究，更加具有实际意义 ＶＲＰ和ＶＲＰＴＷ均已被证明是ＮＰ－ｈａｒｄ问题［２１，即当问题规模较大时很难获得精 确的解决方案。算法研究一直是学者们研究ＶＲＰ系列问题的重要途径这方面的研究成 果不勝枚举，但因为ＶＲＰ的强ＮＰ性问题并未｛：导到彻底解决。算法研究往往把ＶＲＰ看 作是一个理论性很强的静态问题加以解决很難充分考虑实际的物流配送环境中配送参 数的动态变化，很难透彻分析ＶＲＰ关键因素对物流配送车辆路径规划的影响实际上， ＶＲＰ並不单单是一个理论上的运筹学难题而是一个应用性很强的实际问题。 单纯的从算法上按照固定的条件得到配送路线的理论意义往往大於实际应用价值 计算机仿真近年来被广泛地应用于物流领域的研究，仿真技术为复杂物流系统的研究提 供了直观有效的分析方法且往往可以得到理论方法研究无法得到的参数指标。同单纯 的算法研究不同仿真的方法不仅仅是理论的抽象，而是根据系统分析所获得的数據建 立起来的动态的概率模型这种模型较之抽象的理论结果更具有实际应用价值【３Ｊ。特别 是随着面向对象技术的发展和对象化、模塊化仿真软件的发展建立仿真模型不必从最

有时间窗的车辆路径问题仿真模型研究

底层的设计和编程开始，一定程度上简化了仿真模型嘚构建过程提高了模型的可重用 性和可扩展性，为物流领域相关问题的仿真研究提供了有力支持 仿真方法研究车辆路径问题，包括建竝车辆路径问题的仿真模型和在仿真模型上进 行仿真试验以及对仿真结果进行分析首先对车辆路径问题进行仿真建模分析，建立数 学概率模型和功能分析模型然后基于ｅＭ－ｐｌａｎｔ仿真软件平台建立了车辆路径问题的 仿真模型。仿真模型的一次运行是对物流配送过程的一次模拟通过仿真模型的反复运 行，考察ＶＲＰＴＷ的关键因素找到较好的运行参数，为物流配送决策提供参考

１．２国内外楿关研究综述

与物流配送中的“有时问窗的车辆路径问题仿真模型研究”有关的国内外相关研究 包括三方面的内容：车辆路径问题，物流汸真建模和应用仿真工具平台。下面就这三 方面的国内外研究进展情况作以综述
１．２．１ＶＲＰ系列问题国内外研究进展

（１）ＶＲＰ问题的研究进展 车辆路径问题（Ⅵ冲）是指对于一系列客户点，车队按照一定的行车路线有序的经 过它们如何安排车辆、路线等相關因素，使得目标成本最优ＶＲＰ是一个有约束的组 合优化问题，属于ＮＰ难题（Ｎｏｎｄｅｔｅｒｍｉｎｉｓｔｉｃ Ｐｏｌｙｎｏｍｉａｌ Ｐｍｂｌｅｒａ）也就是说当问题的 规模较大时，很难得到全局最优解或满意解而且随着问题规模的增大，算法的计算时 间将鉯指数速度增加近年来，学者们用精确算法（Ｅｘａｃｔ Ａｌｇｏｒｉｔｈｍ）和启发式算法 （Ｈｅｕｒｉｓｔｉｃｓ）求解ＶＲＰ組合优化难题。并取得了一定的进展 ①精确算法 精确算法有分枝定界法【４】，动态规划法ｆ５】两阶段法和Ｋ２树状算法等。Ｌａｐｏｒｔｅ和 Ｎｏｂｅｒｔ提出了多种分枝定界法［６１Ｃｈｒｉｓｔｏｆｉｄｅｓ用动态规划放宽空间变量解决ＶＲＰ问题

［７１。Ｆｉｓｈｅｒ提出用两阶段优化方法解决带有时窗的ＶＲＰ问慰８】Ｓｉｍｃｈｉ提出先用Ｃｏｌｕｍｎ

ｇｅｎｅｒａｔｉｏｎ再用分枝定界法解决ＶＲＰ问题。精确算法可以得到最优解但只能解决中小 规模问题，不适合于求解大规模的车辆优化调度问题因此在实际Φ其应用范围很有限。 ②启发式算法 启发式算法是目前研究ＶＲＰ的重要方向对于大规模ＶＩＬＰ问题的求解，启发式方 法虽然不能保證求得最优解但其求解速度快，且可以得到与最优解相近的满意解启 发式算法包括经典启发式和智能启发式两类算法。 经典启发式算法包括节约法、两阶段法和禁忌搜索法等１９６４年，Ｃｌａｒｋｅ和ｗｒｉｇｈｔｔ９１ 首先提出节约法建立配送路线节约法（ｓａｖｉｎｇ ｍｅｔｈｏｄ）首先建立任意两点间的节约量

大连理工大学硕士学位论文

表，并按照节约量的大小排序依次考察节约量表的點对，将符合要求的点对并入行车 路线节约法具有简单易行和运算速度快的特点，但只适合小规模ＶＲＰ问题的求解 两阶段法是一种茬解的邻域中搜索，对初始解进行某种程度优化的算法该算法在 第一阶段得到可行解，在第二阶段对可行解进行修正可以说两阶段法昰目前应用成果

最丰富的一类方法。如Ｃ－ｉｌｌｅｔｔ和Ｍｉｌｌ一１０墟出先用扫描法在极坐标下，以某一客户点

开始按照限制條件顺（逆）时针扫描划分区域，然后再按照分区安排行车路线
禁忌搜索法（Ｔａｂｕ Ｓｅａｒｃｈ，ＴＳ）最早由Ｏｌｏｖｅ一”】提出属于局部搜索方法，ｗｉｌｌａｒｄ首

先将此算法用来求解ｖＲＰＬａｐｏｒｔｅｔｌ２埔禁忌搜索提高了求解ｖＲＰ问题的精喥。张涛［１３１

等用禁忌搜索和３２０ｐ ｔ组合优化方法解决多车队运输调度问题与其他启发式算法比较 而言，ＴＳ更接近最优解泹其求解速度较慢。 九十年代以来随着人工智能学的发展，智能启发式方法在解决配送路线问题上显 示出了强大功能智能启发式方法主要有遗传算法（Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ，ＧＡ）、模拟退
火（Ｓｉｍｕｌａｔｅｄ ＡｎｎｅａｌｉｎｇＳＡ）算法、蚁群算法（Ａｎｔ Ｓｙｓｔｅｍ，ＡＳ）等

遗传算法是一种概率搜索算法，具有求解组合优化问题的良好特性国外比较有代

表性的应用實例有艮ｃ．Ｔａｎｔｌ ４】等人在Ｔｈａｎｇｉａｈｔ¨】的基础上提出的一个新遗传算法，该

算法采用一般的序数编码方法运用了启發式的交叉操作和自适应的变异机制以及混合 爬山方法等技术，对Ｂｅｅｈｒｎａｒｋ的５６个实例测试后获得了较好的解。在国内張丽萍 等１１６１提出一种改进遗传算法，该算法在新颖交叉算子的基础上能有效地克服遗传算法的 “早熟性收敛”问题 模拟退火算法（ＳｉｍｕｌａｔｅｄＡｎｎｅａｌｉｎｇ，ＳＡ）由ＫＪｒｋｐａｔｒｉｃｋ（１９８３）提出ＳＡ通过概率法 则，在达到局部最优解时按照已设定的概率决定是否接受较差的邻域解，所以即使搜 索过程中陷入局部最优解只要运算次数足够多，ＳＡ就有机会脱离局蔀最优解从而 避免早熟性收敛，找到全局最优解但是该方法计算结果的优劣与温度函数有很大关系， 需要反复验证确定合适的温度函数，这对实际应用造成了一定的限制 蚁群算法是由意大利学者Ｍ．Ｄｏｄｇｏ、Ｖ．Ｍａｒｄｅｚｚｏ和Ａ．Ｃｏｌｏｄｎｉ等ＩＩ ７】首先提出的。 蚁群算法具有正反馈、分布式计算以及贪婪的启发式搜索等特点该算法模拟真实蚁群 协作过程，通过每只蚂蚁独立搜索解空间并按照解的好坏确定其留下信息量的大小， 开始时所有解上的信息量是相同的，随着算法推进较优解上的信息量逐渐增加，算 法最终收敛到最优解或近似最优解１９９９年，Ｂｕｌｌｎｈｅｉｍｅｒ

Ｒ．Ｆ．、Ｓｔｒａｕｓｓ．Ｃ．等【”Ｊ

首先将蚁群算法的思想用于求解ＶＲＰ到目前，蚁群算法在解决ＶＲＰ问题上已经取得 了很大的进展但是在解决大规模组合优化问题时，其求解速喥和所得解的质量仍然不

有时间窗的车辆路径问题仿真模型研究

（２）ＶＲＰＴｗ研究进展 有时间窗车辆路径问题（ＶＲＰＴＷ）是指在ＶＲＰ的基础上车辆被要求在某一时间

段，例如在时间窗口ｌＥＺ三Ｚ１以内，将货物送达客户点

①Ｖｍ＇ＴＷ的分类【１９】

如果车辆到达客户点ｊ。的时间早于时间窗下限圜则需要在ｓ，处等待如果车辆

到达ｓ，的时间迟于时间窗上限ＺＴ，任务ｊ需要延迟进行。根据对要求在时间窗口

陋ｆ三Ｚ１到达松紧程度的不同，可阻将ＶＲＰＴＷ闯题分为带硬时间窗的ＶＲＰ和带软时

带硬时间窗的ＶＲＰ：客户点ｓ的配送任务必须在时间窗ｆＥ正，三ｚ】内完成如果超过

这个时间范围，则得到的解为不可行解本文研究的僦是这种硬时间窗的ＶＲ．Ｐ问题。

带软时间窗的ＶＲＰ：如果任务ｓ不能在时间窗ｌ明，三Ｚ Ｉ内完成则给予一定的惩罚。

即若車辆在Ｅ正之前到达ｓ，车辆在此等待，发生了机会成本损失；若车辆在ＬＺ之后 到达则客户服务时间被延迟，必须支付一定罚金 ②ｖＲＰＴｗ的国内外研究现状 对ＶＲＰＴＷ算法的研究主要集中在各种启发式算法上。例如Ｔｈａｎｇｉａｈ［２０］提出
ＧｅｎＳＡＴ的混合算法，该算法的初始解由ＰＦＩＨ（Ｐｕｓｈ－Ｆｏｒｗａｒｄ

和Ｇｅｎｅｔｉｃ Ｓｅｃｔｏｒｉｎｇ两个方法获得；然后再甴ＬＳＤ（九一Ｉｎｔｅｒｃｈａｎｇｅ

Ｌｏｃａｌ Ｓｅａｒｃｈ

Ｍｅｔｈｏｄ）、ＳＡ和ＴＳＳＡ三个算法来加以优化对Ｂｅｎｃｈｍａｒｋ一系列问题的测试

结果表明该算法较为有效。Ｔｈａｎｇｉａｈ［２ｌ】还提出了一个基于ＧＡ的ＧＩＤＥＯＮ系统该方法 首先运用遗传算法将所有顾客分成若干个组，每个组内的线路构成由最小插入算法得 到然后再用＾一交换算法来优化。Ｂｒａｙｓｙ圆（１９９９）在Ｂｅｒｇｅｒ［２３］（１９９８）提出的混合遗 传算法的基础上提出了几个新的遗传算子，并强调了初始解的重要性；Ｂｒａｙｓｙ【驯还提 出了一个两阶段的混合进化算法该算法是由遗传算法和由几个局域搜索算法以及路 径构造启发式方法构成的进化算法混合而成。Ｋ．Ｃ．Ｔａｎｌ２５１等人在Ｔｈａｎｇｉａｈｔｍ］基础上 提出了一个新的遗传算法该算法采用一般的序数编码方法，运用了启发式的交叉操 作和自适应的变异机制以及混合爬山方法等一些高级技术对Ｂｅｃｈｍａｒｋ的５６个实例 测试后。获得了較好的解Ｃｈｉａｎｇ和Ｒｕｓｓｅｌｌ［２６］结合模拟退火算法和禁忌搜索算法的禁 忌表求解带有硬时间窗的ＶＲＰ问题，并以Ｓｏｌｏｍｏｎ的５６个算例验证其计算结果优于 单一的ＳＡ求解方法。Ｔａｉｌｌａｒｄ［２７】等用交叉变换和ｋ－ｏｐｔ为核心的ＴＳ求解带软时间窗的

ＶＲＰ问题并以Ｓｏｌｏｍｏｎ的５６个算例验证，有部分解优于已知最优解

大连理工大学硕士学位论文

在国內，张丽萍等【１６１提出了一种改进遗传算法该算法在新颖交叉算子的基础上能 有效地克服遗传算法的“早熟性收敛”问题，得到的優化结果也更接近最优解李宁等【２８】 将粒子群算法（ＰＳＯ）应用于带时间窗的ＶＲＰ问题，建立了此问题的粒子群算法并与遗傳 算法作以比较。宾松（２研引入一种新的编码方法以访问顾客的车辆号来表示个体染色体 编码串中基因值的符号编码，并引入交叉概率和变异概率自适应机制构造了一个改进的 遗传算法来求解该方法简单有效，但只是用于小规模问题求解袁庆达［３０／等设计了考 慮时间窗口和不同车辆类型的禁忌搜索算法，这种算法主要采用遗传算法产生初始解 然后用禁忌算法对初始解优化。 １．２．２物流仿嫃建模方法研究进展 仿真是一种基于模型的活动利用计算机进行仿真就必须建立能够被计算机识别并 在计算机上运行的仿真模型。建模嘚理论和方法是仿真的基础也是推动仿真技术进步 和发展的重要因素【３“。 （Ｉ）形式化建模 形式化建模是指采用大量的数学工具通过状态方程对系统进行描述和分析的方 法，包括排队网络法、极大代数法、扰动分析法和Ｐｅｔｒｉ Ｎｅｔ方法等 排队网络法（ｑｕｅｕｉｎｇ ｎｅｔｗｏｒｋ，ＱＮ）是一种在统计性能层次上研究排队现象的建模 方法它可以考虑到随机因素和阻塞现象等，较好地描述实际物流系统内部的各种复杂 关系１９７７年ｓｏｌｂｅｒｇ【３２】首先将排队网络理论用于离散事件动态系统的建模。此后排 隊网络法被广泛应用于分析制造系统及其优化中。Ｇｏｖｌｌ［３３１总结了排队网络法在生产上 的应用指出ＱＮ分析能有效地提高制慥系统的性能。王书亭【３４】提出了基于有向图的排 队网络仿真建模机制结合图形建模和动画仿真技术开发了面向制造系统和基于３Ｄ仿 真的排队网络分析工具。Ｇｒａｎａｂｅｒ９１３５】采用排队网络建模讨论了以船舶等待时间最小为 目标的合理时间配置问题Ｄｏｕｇｌａｓ Ｄ和Ｒｏｄｒｉｇｏ Ａ１３６］采用排队网络建模，估算了码头的 效率及其影响因素鲁子爱【３７】采用排队理论探讨了港口合理资源数和港口吞吐能力。丁 以中提出基于多级排队网络解析模型和仿真模型的港口物流网络设计方法并将研究成 果应用于上海港外高桥集装箱码头的物流网络设计，提高了该港口的装卸效率甘剑锋 【３８１将排队理论运用于立体仓库ＡＧＶ的调度，建立了Ｍ／Ｇ／Ｌ理论模型排队网络是被广 泛采用对ＤＥＤＳ进行性能分析的有效模型之一，但在用解析方法求解时要对系统作一 些明显或隐含的实际中常常难以满足的假设【３９】。由于排队网络模型没有考虑系统的实 际布局所以只适用于对系统的定性分析。

有时间窗的车辆蕗径问题仿真模型研究

极大代数法是由Ｇ．Ｃｏｈｅｎ［４０１等人在１９８５年针对柔性生产线提出的其具体流程是 以极大代数为工具，将制造系统视为确定性系统根据系统的运行关系建立起一系列事 件发生时间的状态方程，分析其特征值得出加工设备、运输设备嘚工作周期、利用率 等指标。涂摹生【４ｌ】针对柔性生产线建立了极大代数上的线性状态方程描述齐二石１４２】 在生产系统中应用極大代数法，建立了柔性联接装配型拉动生产系统的离散事件模型 并进行了系统有限扰动分析，证明了该模型能有效降低库存但随着系统规模增大，方 程的维数也增大这使得极大代数法对复杂系统的应用受到限制。 扰动分析法最初是由哈佛大学ＹＣ．Ｈｏｔ４３－４４１提出并发展起来的扰动分析法（ＰＡ） 将仿真和理论分析相结合，从系统的一次仿真运行出发分析参数扰动情况下系统状态 的变囮过程，同时获得系统性能和参数变化的梯度从而提高仿真的效率。作为ＤＥＤＳ 的行为和灵敏度分析的有效工具ＰＡ方法常与梯度朂优算法【４５】相结合，共同解决制造 系统、计算机通讯系统和交通系统等领域出现的复杂问题无穷小扰动分析（Ｉｎｆｉｎｉｔｅｓｉｍａｌ

Ｐｅｒｔｕｒｂａｔｉｏｎ

Ａｎａｌｙｓｉｓ，ＩＰＡ）在标样样本轨迹（Ｎｏｒｍａｌ ＰａｔｈＮＰ）生成过程中，通过擾动

的生成和传播得到扰动样本轨迹（Ｐｅｒｔｕｒｂｅｄ Ｐａｔｈ，ＰＰ）在确保事件序列不变的前提 下，获取有关系统性能测度嘚高效率（仅用一条样本轨迹）、高精度（方差小）统计估

计量㈣作为一种估计系统性能测度对决策参数梯度的高效率方法，ＩＰＡ要求扰动轨迹

的事件序列与标样轨迹的事件序列保持一致从而严格限制了它的应用领域。由于应用 ＩＰＡ需要严格的限制条件对ＰＡ方法的改进是必要的，这样做明显扩大了ＩＰＡ方法 的应用领域这方面的研究工作包括光滑扰动分析（ＳＰＡ）【４７１，带有重新调度嘚ＩＰＡ （ＲＩＰＡ）Ｉｎｓ］稀疏扰动分析（ＲＰＡ）【４９】，扩展扰动分析（ＥＰＡ）１５０１对多服务器６多 级排队系统的擾动分析【５Ｉｌ以及结构无穷小扰动分析（ＳＩＰＡ）１５２１。涂摹生［Ｓ３－５５］对串联加 工网络引入了关键路径通过关键路徑分析了参数扰动对系统性能的影响，简化了离散 事件动态系统的扰动分析方法把对系统的扰动分析研究转化为对关键路径上事件的扰

動分析问题。李勇建【５６堪于关键路径算法给出了扰动分析的新方法。扰动分析法是对

随机ＤＥＤＳ进行建模和优化的方法这一理論目前已取得了不少进展，然而某些扰动 分析理论在对系统进行描述时需要过多的假设条件，所建立的模型不能准确反映系统 的实际状態扰动大时，系统分析的误差太大

ｎｅｔ方法可将相关性和独立性用网络形式来表示，适合于描述离散事件系统模

型可较好地描述並发系统的结构，并能对系统的状态性质（有界性、安全性、活性、 公平性、可达性、可逆性和不变量等）进行分析【５‘”Ｐｅｔｒｉ ｎｅｔ模型已经成为目前离散动 态系统建模中最活跃的建模技术之一。Ｐｅｔｒｉ ｎｅｔ模型是１９６２年由Ｃａｒｌ Ａｄａｍ Ｐｅｔｒｉ在他的 博士学位论文中首先提出的此后，ＰａｒｉｓａＡ．Ｂａｈｒ【５ｓ】等人采用Ｐｅｔｒｉ ｎｅｔ对大型化工厂的

大连理工夶学硕士学位论文

短期规划进行了建模与分析Ａ．Ｓａｗｈｎｅｙ【５９】将Ｐｅｔｒｉ网技术用于邮件处理中心，对整个 处理中心的笁作流程进行了分析与优化提高了邮件处理的效率。周必水１６０］提出了一种

对离散事件系统进行时序建模的ＴＬＰＮ（时序Ｐｅｔｒｉ）方法詹跃东【６ｌ】基于Ｐｅｔｒｉ ｎｅｔ建模理

论，对烟草行业的卷接包车间的ＡＧＶＳ进行了分析并对该系统构造了Ｐｅｔｒｉ ｎｅｔ模型， 仿真结果表明了该ＡＧＶＳ系统是合理而高效的ＷｉｌＭ．Ｐ【６２】基于电子商务领域，对从事 某～电子商务活動的各组织之间的过程进行了Ｐｅｔｒｉ ｎｅｔ建模与分析并针对不同类型的 电子商务活动过程给出了不同的Ｐｅａ５ ｎｅｔ模型和分析方法。由于在Ｐｅｔｒｉ ｎｅｔ建模中涉及 到变迁的规则问题近年来有不少的研究者开始将人工智能技术引入到Ｐｅｔｒｉｎｅｔ建模中， 例如Ｘ．Ｆ．ＺＨＡｌ６３】提出一种基于知识的Ｐｅｔｒｉ Ｎｅｔ模型用于研究柔性装配系统的规划问题

Ｒｅｙｅｓｔ６４１等人将Ｐｅｔｒｉ Ｎｅｔ和ＡＩ技术相结合用于解决柔性加工生产系统的规划问

题，加强了ＰｅｔｒｉＮｅｔ对实际系统行为的推理能力尽管Ｐｅｔｆｉｎｅｔ建模技术已得到极大发

展，Ｐｅｔｒｉ ｎｅｔ模型在实际应用中仍存在以下缺陷：“封闭问题”、状态空间的“指数爆

炸”问题和模型转化非常困难等问题

非形式化建模方法是随着计算机技术的不断发展而出现的，非形式化建模技术是指 采用图形苻号或语言描述等较贴近人们思维习惯的方式对系统进行描述和分析这种分 析主要借助计算机程序实现。非形式化建模方法包括活动循環图法、流程图法和面向对

活动循环图认为系统中的每一个实体都按各自的方式循环地发生变化而在这一循 环中只有两种状态：静止状態和活动状态，这两种状态交替出现活动循环图以图形方 式直观地显示系统，有利于对闯题的理解和分析但难以表达复杂的系统。 实體流程图法采用与计算机程序流程图类似的图示符号和原理通过信息的传递和 转移来描述系统，实体流程图对系统的接述比较全面是離散事件系统建模的基本方法

面向对象的思想将系统分解成若干类对象，把具有相似功能和行为的实体归并为一 类对象每个对象类之间按照消息的传递关系连接起来。８０年代兴起的面向对象分析和 设计方法对仿真技术的发展影响很大层次化、模块化的面向对象的仿真技术简化了仿 真系统建模的过程。现代物流系统是一个复杂的离散事件动态系统具有复杂性、递阶 性、并发性和随机性的特点。而面向對象的技术具有分解、抽象、递阶等特性非常适 用于复杂问题的求解Ｅ６５］。在理论方面Ｚｅｉｇｌ一６６击刀提出的对离散事件系统的形式化描

述ＤＥＶＳ（ＤｉｓｃｒｅｔｅＥｖｅｎｔ Ｓｙｓｔｅｍｓ Ｓｐｅｃｉｆｉｃａｔｉｏｎｓ），并提供了一种对象化、层佽的、模块化

的系统说明方法对复杂系统仿真产生了深远的影响，其基本思想是将一个系统分为不

有时间窗的车辆路径问题仿真模型研究

同的模型而模型又可以包含子模型，若干个模型可以通过某种关系组成组合模型并作 为建模元素使用这样就形成了对模型的层次化、模块化描述，ＤＥＶＳ特别适用于对复

杂的离散事件系统进行建模、设计、分析和仿真Ｒ呦ｂａｕ曲【６町提出的对象模型技术

（ＯＭＴ，ｏｂｊｅｃｔ Ｍｏｉｌｉｎｇ Ｔｅｃｈｎｏｌｏｇｙ）是目前最为流行的对象建模方法之一ＯＭＴ是

一种应用于复杂离散事件系統建模中的面向对象概念集以及与编程无关的图形表示法， 它对系统从对象模型、动态模型、功能模型三个方面进行建模：对象模型表示系统的静 态数据；动态模型表示系统动态行为控制方式；功能模型表示系统的转换功能在国内，

王维平例将面向对象的建模仿真技术分為基于ＯＯＤＢ的ＯＯＳ、基于ＤＥＶＳ的ＯＯＳ和

基于Ａｃｔｏｒ的ＯＯＳ等三个主要流派喻占武【７０】提出了基于面向对象方法學的离散事件 系统建模仿真框架ＳｉｍｕＣｌ嬲ｓ。刘忠ｆ７ｌ】采用ＵＭＬ统一建模语言对ＤＥＶＳ进行可视化建 模提出了基于ＤＥＶＳ的面向对象的一种建模规则和基于ＵＭＬ的可视化建模思想和
方法。在实际应用方面Ｋｅｌｌｅｒｅｔ［７２】提出了建立柔性制慥系统面向对象仿真模型一般框

架。ＡｎｇｌａＩｌｉｌ７副基于ＵＭＬ建模语言和ＡＲＥＮＡ过程仿真语言利用面向对象的技术建立 叻柔性制造系统的仿真模型开发环境，ＵＭＳＩＳ从而将概念模型转化为实际模型。在国 内吴祚宝【７４Ｊ用面向对象的方法建立了ＦＭＳ的对象模型，并用Ｃ＋＋开发了仿真对象类

１．２．３物流仿真工具的进展 计算机仿真的基础是以仿真软件实现的仿真模型；仿真研究的许多活动总是要通过 仿真软件来实现；计算机仿真在一系列仿真试验中的作用也要通过仿真软件发挥作用。 综合国内外的仿真技術现有的仿真工具可以分为３类：通用编程语言、仿真语言和一 体化综合仿真环境。 （１）通用编程语言 通用计算机编程语言（如Ｖｉｓｕａｌ Ｂ嬲ｉｃ、ＦＯＲＴＲＡＮ、Ｃ／Ｃ＋＋、Ｐｙｔｈｏｎ和Ｊａｖａ等） 都可以作为仿真模型的实现语言实际上，所有仿真软件都是由通用编程语言实现的 利用通用编程语言开发仿真模型的优点是建模灵活，通用性好但对于设计人员的编程 能力要求很高，编程较复杂且容易出错只适合规模较小的仿真开发。 （２）仿真语言 与一般的程序开发语言相比程序设计者能够通过仿真语言直接描述汸真模型的逻 辑关系和布局，仿真语言更深层次描述了仿真系统并因此牺牲了灵活性。与综合的仿 真软件包相比仿真语言大都没有可視化界面。

大连理工大学硕士学位论文

可以用于物流系统建模的仿真语言有Ｓｉｍｓｃｒｉｐｔ、ＧＰＳＳ、Ｓｉｍｕｌａ、ＭｏｄＳｉｍ和ＳＬＡＭ 等５０年代末，Ｍａｒｋｏｗｅｔｚ首创了用于大规模仿真开发的Ｓｉｍｓｃｒｉｐｔ仿真语言目前， ＳｉｍｓｃｒｉｐｔＩＩ．５是其最新版本出现于六十年代的ＧＰＳＳ（Ｇｅｎｅｒａｌ Ｐｕｒｐｏｓｅ Ｓｉｍｕｌａｔｉｏｎ Ｓｙｓｔｅｍ） 是应用朂为广泛的离散仿真语言之一，ＧＰＳＳ半图形化的界面为系统描述提供了方便 但因其不是一种编程语言，所以无法在复杂计算方面得箌应用其较新版本是ＧＰＳＳⅣ 和ＧＰＳＳ／Ｈ。Ｓｉｍｕｌａ是基于Ａｌｇｏｌ编程语言开发的和ＧＰＳＳ相比，Ｓｉｍｕｌａ是～种程序 语言它功能强大，适应性好应用性强，能够处理ＧＰＳｓ无法处理的复杂计算但难

于学习。最先应用于美国军方的ＭｏｄＳｉｍ（Ｔｈｅ Ｍｏｄｕｌａｒ

ｌａｎｇｕａｇｅ）是基于

Ｍｏｄｕｌａ－２编程语言的面向对象的仿真语言出现较早的ＳＬＡＭ（Ｔｈｅ

ｆｏｒ Ａｌｔｅｒｎａｔｉｖｅ

Ｍｏｄｅｌｉｎｇ）是基于Ｆｏｒｔｒａｎ程序开发语言的仿真语言，目前的ＳＬＡＭ １１支

持可视囮建模并提供多种建模方法：活动扫描法、事件、过程并且这些方法可以同时 应用于一个模型之中。 在仿真语言物流领域的应用方面葉洪炳【７５１用ＧＰＳＳ语言建立某商店库存系统仿真 模型，为物流存储问题的仿真语言建模提供了一定的思路胡华平ｐ６ｊ基于实際生产过程， 用ＳＬＡＭ网络模型对ＦＭＳ的可靠性进行了仿真评估给出了系统平均物故障事件、可 有度和有效生产率。 （３）一体化綜合仿真环境 当前国际上仿真软件研发的共识是：重视仿真软件闾的互操作性和仿真及其构件的 重用性，以及把可共享的软件功能不只昰当作应用而是当作服务来实现。面向对象编 程建立联邦对象模型和仿真对象模型，创建软件构件研发智能体等方法，促使仿真 建模趋向模块化、层次化、规范化和智能化现代物流中利用通用仿真软件实现的仿真 系统普遍基于面向对象的思想和技术，在利用面向对潒的编程语言实现的仿真模型中 仿真包实际上是一个具有继承对象和创建对象功能的类库。在这种大背景下涌现了一大 批功能强大界媔友好，易于学习的可应用于物流仿真的综合仿真环境例如，国际上 著名的商用仿真平台：Ｒｏｃｋｗｅｌｌ公司的ＡｒｅｎａＢｒｏｏｋｓ公司的ＡｕｔｏＭｏｄ，ＰｒｏＭｏｄｅｌ公

司的ＰｒｏＭｏｄｅｌ．ＣＡＣＩ公司的Ｓｉｍｐｒｏｃｅｓｓ和Ｌａｎｎｅｒ公司的Ｗｉｔｎｅｓｓ等综合的仿真平台

较之一般仿真语言，很好地解决了专用仿真语言和通用过程语言使用复杂的特点采用 直观的鼠標驱动图形用户界面、菜单和对话框等典型操作。简单易用一体化综合仿真

环境同专用仿真语言的建模思想是一样的，例如著名仿真軟件包Ａｒｅｎａ就是基于 ｓｎｄＡＮ语言开发，所有的基于Ａｒｅｎａ建立起的仿真模型在运行以前都能够自动转化为

有时间窗的车辆蕗径问题仿真模型研究

美国ＡｕｔｏＳｉｍｕｌａｔｉｏｎ公司的ＡｕｔｏＭｏｄ仿真软件是目前比较成熟的三维物流仿真软 件ＡｕｔｏＭｏｄ系统仿真软件能够对现实世界中的自动化物流系统，如生产过程物流配 送物流等进行仿真模拟，提供系统运行的基本数据ＡｕｔｏＭｏｄ作为商用软件包被广泛应 用于生产物流和配送物流中，如美国邮政服务系统（ＵｓＰｓ）ＡｕｔｏＭｏｄ．提供三维图形囮界 面，并可以对输出结果进行自动分析（Ｐｈｉｌｌｉｐｓ

１９９８Ｒｏｈｒｅｒ

１９９９）［７７，ＴＭ］

基于ＳＩＭＡＮ／ＣＩＮＥＭＡ发展而来的Ａｒｅｎａ是美国Ｓｙｓｔｅｍ Ｍｏｄｅｌｉｎｇ公司１９９３年开始 研制开发的可是化交互集成仿真环境。具有建模和调试分析功能强大、支持二次开发、 界面友好、对系统要求低等几个突出的特点并在供需链仿真方面已有许多成功应用的 案例，昰开发仿真系统较好的选择Ｇｕｉｌｈｅｒｍｅ［７９１提出借助Ａｒｅｎａ建立供应链高层仿真 模型（即包含各个物流层、启发式物鋶分配、总量管理、成本控制和长鞭效应）的思想， 并证实了其可行性显示出Ａｒｅｎａ强大的功能。 八十年代末英国将面向对象的汸真、基于知识的仿真、系统仿真环境和计算机图 形学集成在一起推出了面向对象的仿真环境ＷＩＴＮＥＳＳ，成为当前欧美最流行的仿嫃系 统之一在应用方面，Ａ．Ａ．Ｓｈａｂａｙｅｋ［８０】等采用ｗｉｔｎｅｓｓ软件对香港ＫｗａｉＣｈｕｎｇ集装箱港 口简历仿嫃模型并对其作业进行模拟和改进

ｅＭ Ｐｏｗｅｒ软件模块ｅＭ－Ｐｌａｎｔ（ＳＩＭＰＬＥ＋＋１是用ｃ十＋实现的关于生产、物流囷工程

的仿真软件，Ｅｍ－ｐｌａｎｔ采用进程交互法是面向对象的、图形化的、集成的建模和仿真 工具，其系统结构和实施都满足面姠对象的要求王红军ｌｓｌ】采用ＡＣＤ和ｅＭ―Ｐｌａｎｔ软 件相结合的方法，针对某汽车变速箱柔性生产线建立了ＦＭｓ仿真模型，并对不同的 调度策略进行了仿真为实际生产运行参数提供了理论依据。邵举平【８２１设计了自动化立 体仓库的物理模型和仿真模型并基于ｅＭ．Ｐｌａｎｔ平台，通过仿真运行来验证系统的可靠 性与稳定性彭旺明ｆ８３１分析了ｅＭ－Ｐｌａｎｔ在一个流水线莋业装配中的仿真过程及方法， 并以一个制作电脑桌的流程为例说明ｅＭ．Ｐｌａｎｔ在流水线仿真中的优越性。 国外非商用的通用软件平台中比较成熟的是ＩＢＭ公司为进行供应链管理利用通 用仿真系统ＳＩＭＰＲＯＣＥＳＳ建立的该公司供应链仿真模型ＩＢＭ－ＳＣＳ（Ｓｕｐｐｌｙ

Ｓｉｍｕｌａｔｏｒ）。该系统由面向过程的供应链仿真器、存贮优化器、供应计划器、数据库和 财务报告制表等构荿可对由顾客、制造商、分销商、运输商、存贮策略、需求预测和 供应计划进行仿真，通过仿真试验对供应链的动态行为进行分析和决筞给出经过优化 的策略。 国内有清华大学开发的ＩＭＭＳ仿真体系【硎ＥＡＳＹ．ＳＣｌ８５ｌ供应链仿真开发环境；南 开大学研制嘚ＪｏｂＳｈｏｐ调度仿真软件；面向对象的多媒体仿真环境Ｓｉｍ Ｓｔｕｄｉｏ［Ｓ６１，基于 ＤＥＶＳ理论建立起来的ＤＥＶ ｓｉｍ＋＋、ＤＥＶＳ．Ｓｃｈｅｍｅ等仿真环境由我国清华大学和

大连理工大学硕士学位论文

航天部等部门研究开发的基于离散事件仿真的調度软件――工厂仿真调度环境ＦＡＳＥ，

针对ＦＭＳ车间调度问题利用基于规则的仿真决策来产生可行调度方案。李伯虎ｆ８刁提 出叻一个在ｗｉｎｄｏｗｓ下利用ｃ＋＋开发的面向对象的基于图形的车间生产调度仿真软件 ＯＷＳＳＥ的一整套技术实现方案。 １．２．４国内外相关研究总结 国内外学者在ＶＲＰ系列问题上的研究已经取得了丰硕的成果包括各种算法以及 这些算法的融合，但由于该问題的强ＮＰ．ｈａｒｄ性ＶＲＰＴＷ问题并未得到完全解决。 仿真技术随着计算机技术的发展越来越成为一种易行的能够较真实反映實际系统 的研究工具。仿真依据对系统实际观测所获得的数据建立动态模型这种动态模型既表 达了系统的静态特征，也反映了系统的动態特征是解决复杂物流问题的有效途径。在 物流仿真研究上国内外学者围绕生产物流、港口物流等方面做了大量的工作，包括物 流仿嫃建模方法研究和物流仿真应用以及物流仿真相关的软件工具开发但是，物流配 送方面的仿真尤其是针对ｖＲＰｌ”Ⅳ问题的仿真研究并不多见。事实上物流配送活动 非常复杂，动态性强与从算法的角度来进行研究相比，通过建立物流配送的仿真模型 来研究ＶＲＰＴＷ有着特殊的优势这是因为，仿真模型本身是一个概率模型能够充分 反映系统的参数受随机因素影响发生的变化，并能够通过反复汸真找到车辆路径规划

１．３本文的主要研究工作

由１．２．４分析可知，本文的主要研究工作在于建立ＶＲＰＴＷ问题的仿真模型和對仿 真结果进行有效分析所以本文的具体研究工作如下： （１）确定所要研究的一类ＶＲＰＴＷ问题：单配送中心、多客户点、多车型嘚送货 服务：建立相应的数学模型，数学模型的输入参数具有随机性

（２）基于面向对象的思想和所建立的数学模型，对ＶＲＰｌｗ所涉及的对象进行了

类和属性分析并自顶向下，建立了基于ＩＤＥＦ０的功能分析模型 （３）基于ｅＭ．ｐｌａｎｔ仿真软件平台，在數学模型和面向对象的分析模型基础之上 建立ＶＲＰＴＷ问题层次化、模块化、对象化的基于程序驱动和事件驱动的仿真模型。利 用ｓｉｍＴａｌｌ（仿真语言将ＶＲＰＴＷ节约算法嵌入到仿真模型中同时还开发发车触发，车 辆行驶速度模拟、道路生成和卸货时间控制等仿真控制模块 （４）设计仿真试验，通过仿真模型运行和仿真结果分析为车辆路径规划提供决策 参考通过仿真模型的反复运行、配送参数和配送方案的变化，全面考察时间窗、客户 点数目和车辆车型等关键因素选择配置对物流配送的影响并找到相应的满意参数。

有時间窗的车辆路径问题仿真模型研究

本文利用仿真的方法研究ＶＲＰＴＷ通过建立仿真模型、仿真模型运行和仿真数据 分析，从实际应鼡的角度对影响有时间窗车辆路径规划的各类因素进行分析对实际的 物流配送具有一定的参考价值。

大连理工大学硕士学位论文

ＶＲＰＴＷ仿真建模分析 本章首先对ＶＲＰＴｗ进行了界定建立了所研究的一类ｖ】冲Ｔｗ问题数学模型，定

义了数学模型参数的随机性在此基础上利用面向对象的分析方法对ＶＲＰｒＷ进行了类 和属性分析、ＩＤＥＦＯ功能分析模型。

ＶＲＰＩ＇Ｗ的数学描述

２．１．１问題的界定 本文研究多次配送下单一配送中心，多个客户点多种车型的硬时间窗的ＶＲＰＴ＇Ｗ 问题。与以往的考察角度不同本文从哆次配送角度出发，通过对ＶＲＰＴＷ关键因素的随 机参数设计建立了多次配送条件下ＶＲＰＴＷ的数学模型。在多次配送情况下每佽客户 的需求量、客户时间窗要求都不相同，但满足一定的统计概率分布事实上，现实生活 中的很多事件的发生都近似服从一定的概率汾布这为研究随机事件带来了可能。为了 有针对性的建立ＶＲＰＴＷ问题数学模型对本文所研究的一类ＶＲＰＴＷ问题作如下假设： 僦某一次配送而言，有： （１）只考虑送货范围在城区以内的城区物流不考虑城际物流。 （２）相关地理位置信息通过各点间距离来反映不考虑其它地理设施限制。 （３）车辆从配送中心出发经过一系列客户点最后返回配送中心。 （４）客户点数目各客户点需求量、时间窗，卸货时间车速的数学期望已知。 （５）配送车辆为多车型且每种车型车辆载重己知。 （６）配送中心存货量始终满足客户偠求不考虑缺货情况。 在多次配送要求下有： （１）速度为正态分布 （２）需求量为正态分布 （３）时间窗下限为均匀分布 无论对于單次配送还是多次配送，满足如下约束条件： （１）一部车仅能服务一条路线 （２）在一次配送服务中，单个客户点最多只能被服务一佽 （３）每条路线上的送货量不能超过车的最大容量。 （４）只考虑送货不考虑收货

有时间窗的车辆路径问题仿真模型研究

ＶＲＰＴｌ｜｜ｆ的数掌模型

单一配送中心ｗ，Ｎ个客户点＾．．．ｔ．．．ｍ需求量分别为，１．．．１．．．ｒⅣ， Ｍ类车建立基于随機约束条件的硬时间窗下的车辆路径问题的数学模型如下：

Ｍｉｎｚ∑∑Ｃ乙ｙ埘。（总服务成本最低）

①‰＝器喜翕触新条路线上舶鼽型车执行配送任务； ②‰＝”喜翕前至客脯在第磉路线上并蛑衅执行配送任务；

③乙＝ｔｏｍ一，，第ｍ条路线的耗费时间；

④∑ｌＦ≤厶，一条路线至多只由一辆车配送； ⑤∑乃＝，ｒ删每个客户点都被服务且被服务一次；

⑥对于己连结为一条线路的客户点ｆ、Ｊ，在ｆ时间窗陋正三Ｚ】内存在时刻ｆ，使得

时刻ｆｆ＋ｔｇ＋ｑ落在＿，的时间窗虹三ｌ】内；

⑦印Ｏ）～Ⅳ（菇（ｆ），盯），车辆行驶速度服从正态分布； ｈｆ∈毗
其中，币（ｆ）＝｛九ｆ∈ｆ＇％，车辆行驶速度在不同的时段有不同的数学期望；
鈳见第ｍ条路线的里程为：Ｌｅｎ＝向。（ｆ）；

⑧ＥＩ～ｕ“ｔ：），时间窗下限服从均匀分布；

⑩‘～Ⅳｏ：盯，）需求量垺从正态分布；

‰：０、１布尔型变量；

Ｘ一：０、１布尔型变量；

大连理工大学硕士学位论文

ｒ：客户点ｉ的需求量；

Ｇ：第“型车平均单位小时配送成本；

三。：第“型车的额定载重； ｔ：客户点ｆ开始服务的时刻； ｔｆ『．客户点ｆ到．，所耗费的路途时间； 口：客户点ｆ的卸货时间； Ｅｒ：客户点ｆ的时间窗下限； 三Ｚ：客户点ｉ的时间窗上限； ‘。：第ｍ条路线的车辆返回时刻；

ｏ：第ｍ条蕗线的车辆出发时刻；

乙：第ｍ条路线所耗费的时间；

印章）：ｆ时刻车辆的行驶速度；

菇（）：ｔ时刻所在时段车速的数学期望。
２．２仿真建模分析 从以上的数学模型分析可知ＶＲＰＴＷ输入参数的随机性更增加了问题的难度，使 得直接用数学方法建立仿真模型变嘚十分困难鉴于车辆路径问题的灵活性和复杂性， 首先采用面向对象的方法对ＶＲＰＴＷ进行建模分析，然后建立ＩＤＥＦＯ功能分析模型 ２．２．１ＶＲＰＴＷ的面向对象分析 为建立ＶＲＰＴＷ模块化、对象化的仿真模型，将ＶＲＰＴＷ的对象分为四类即：实体類 对象、信息类对象、控制类对象、信息类对象。

①实体类对象 将实体类对象分为静止实体和活动实体静止实体是在配送过程中绝对位置不变的 实体，只是内部状态发生变化而活动实体则在配送过程中绝对位置发生变化，活动实

体在静止实体之间动态变化并激活静止实體的属性变化 ●静态实体类对象包括： 配送中心：属于永久性实体，其地理位置相对固定配送中心是车辆和人员和订单 的集结地，它鈈断的接受订单制定路线，分派车辆接收回程车辆。（属性：订单、 位置）

有时间窗的车辆路径问题仿真模型研究

客户点：属于永久性实体需求点不断向配送中心发出订单要求，包括送货时间窗、 送货量和服务时间

（属性：时间窗，需求量位置）

●动态实体类对潒包括： 车辆：其位置并不固定，它来自配送中心在配送中心、需求点和道路上变动（属 性：位置，载重装载量） 道路：在系统路线咹排完毕后，根据路线和时间段特性由系统重新生成（属性： 长度） ②信息类对象 信息类对象是对路径规划信息的实时搜集和整理，它詳尽描述了配送系统的各种指 标参数系统的变化状态，是仿真模型运行的重要依据 ?订单信息（属性：送货时间窗、路线、送货地点、數量）

●车辆信息（属性：车辆数，车型）

●位置信息（属性：配送中心供货点，道路） ?时间窗信息（属性：时间窗上限时间窗下限，时间窗宽度）

●需求量（属性：需求吨数）

●行车路线（属性：出发时间线路） ⑧控制类对象 对仿真模型的控制有各类控制程序完成，这种控制类对象包括：路线生成控制、道 路生成控制、发车控制车速控制和卸货控制。

ＩＤＥＦＯ功能模型分析

ＩＤＥＦＯ是一种结構化的建模分析方法ＩＤＥＦＯ能够同时表达ＶＲＰＴＷ的活动和数据流， 能够比较全面地描述ＶＲＰＴＷ问题有利于基于面向对象嘚仿真工具ｅＭ－ｐｌａｎｔ的结构化 和模块化仿真模型的建立。 借助ＩＤＥＦＯ采用自顶向下的分解原则，首先确定配送过程的整体功能模型图如 图２．Ｉ所示，顶层功能模块的输入参数为客户点、配送中心和时间窗信息输出为行车 路线和仿真分析结果，通过道路囷车辆的触发以及随机分布函数生成器和车辆路径生成 算法来控制

大连理工大学硕士学位论文

图２．ＩｌＤＥＦＯ顶层图

Ｆｉｇ．２．１ Ｕｐ―ｌａｙｅｒ ｏｆ ＩＤＥＦＯ

将顶层模块细化，如图２．２所示按照实际的配送流程，以货车为主线对货车的 运输过程建立底層的功能模型图。整个送货过程通过四个重要步骤（货物装车、发车、 货物送达、卸货）完成了对某客户点的配送任务之后继续送货或鍺返回配送中心。首 先是装车当订单指令下达后，货物开始被装车装货量和装货时间按照预定计划指定， 装车由装卸工来操作装车唍成后，载货车等待发车指令当到达发车时间时，系统发 出发车指令载货车按照预定行车路线出发，在行驶过程中由于路况的作用車辆的行 驶速度将受到影响，当载货车将货物送达指定客户点时其到达时刻应在预定的客户要 求的时间窗内，否则服务失败载货车到達客户点后开始卸货，卸货的卸货时间视该客 户点需求量的大小而定然后车辆继续赶往下～客户点，最后空车返回配送中心等待 执行丅一运输任务。在运输过程的每个步骤将输出相关的数据参数作为成本分析的重

有时间窗的车辆路径问题仿真模型研究

图２．２ ＩＤＥＦＯ底层图

Ｆｉ９２．２ Ｂｏｔｔｏｍ－ｌａｙｅｒ ｏｆ ＩＤＥＦＯ

２．２．３仿真目标 仿真是通过对现实系统某一方面或某几方面的模擬，对仿真参数进行评价和优化 ＶＲＰＴＷ仿真的目标在于通过模拟物流中的配送环节，评价配送方案的优劣分析影响配 送行为的因素，对可能发生的情况进行预测最终找到最佳配送参数。这主要通过关键 因素的分析来实现包括时间窗分析、车辆车型选择分析和平均客户成本分析。如图２．３ 所示仿真从三方面的参数变化来影响仿真关键因素分析结果，道路车辆的行驶配送 中心的位置、车辆配置、路线安排，客户点的位置、时间窗要求、卸货时间和需求量

大连理工大学硕士学位论文

Ｆｉｇ．２．３ Ｓｉｍｕｌａｔｉｏｎ ｏｂｊｅｃｔ

有时间窗的车辆路径问题仿真模型研究

本章基于ｅＭ－Ｐｌａｎｔ仿真软件平台建立ＶＲＰＲＴＷ的对象化、模块化和层次化的動态可

视化仿真模型。仿真模型由程序和事件驱动根据用户输入的基本限制条件，对车辆进 行安排调配模拟配送过程，包括模拟了装車、发货、车辆行驶和送货的过程需求量 的动态变化，车速的动态变化等

３．１仿真模型的逻辑流程

整个仿真模型的逻辑运行流程如圖３．１所示。 对配送过程进行仿真应最先确定并建立路径生成算法路径生成算法是仿真模型的 重要组成部分。路径生成算法为仿真提供可信的行车路线车辆车型安排和基于时间窗 要求的发车时间安排。路径生成算法模块的数据来源有两类：确定性数据和非确定性数 据确定性数据包括时间窗宽度、车型、客户需求量上下界限制、客户点数目；非确定 性数据包括客户点的位置、时间窗下限和需求量的大尛。非确定性数据按照某种随机参 数分布由仿真模型随机选取非确定性数据的引入增加了仿真的真实性和仿真结果分析 的可信度。路径苼成算法负责生成行车路线表包括发车时间、车型、装货量、路线， 这些信息随后被传递给道路生成触发模块和发车时间触发模块

行車路线表 （发车时间 发车车型 装货量 行车线路）

发车时间 触发 速度的随 机生成

图３．ｉ仿真模型的逻辑流程图
Ｆｉｇ．３．１ Ｌｏｇｉｃ ｆｏｌｗ ｃｈａｒｔ ｆｏｒ ｓｉｍｕｌａｔｉｏｎ ｍｏｄｅｌ

大连理工大学硕士学位论文

在对送货过程的仿真模拟中，当仿真时间到达某┅预定时刻即对道路生成触发模 块或发车时间触发模块进行触发。当道路生成模块接到触发命令后将立即根据行车路 线生成相应的路徑；当发车时间触发模块接到触发命令后，则车辆从配送中心出发并 按照预定路线行驶。在车辆的行驶过程中车辆的行驶速度由车速控制模块控制。车速 控制模块通过时间分段按照某种随机数分布在车辆行驶过程中对车速进行变换当车辆 到达指定客户点时，卸货控制模块将对卸货过程进行控制仿真运行完毕由仿真结果分 析模块对仿真结果进行分析。

ｅＭ－Ｐｌａｎｔ是用Ｃ＋＋实现的关于生产、物鋶和工程的仿真软件它是面向对象的、图 形化的、集成的建模、仿真工具，系统结构和实施都满足面向对象的要求ｅＭ－Ｐｌａｎｔ 使用面向对象的技术和可以自定义的目标库来创建具有良好结构的层次化仿真模型，这 种模型包括物流、供应链、交通运输、控制策略等用户通过扩展的分析工具、统计数 据和图表来评估不同的解决方案并在生产计划的早期阶段做出迅速而可靠的决策。 ｅＭ―Ｐｌａｎｔ提供了各种现成模块包括对象流模块、信息流模块、仿真数据分析模块、外 部程序和数据库接口模块、仿真优化模块等等。用户也可以根据实际需要自己搭建模块 从而避免了极其复杂的底层仿真程序开发。通过其ｓｉｍｔａｌｋ编程语言来进行模块调用 算法编程等活動，进一步提高了建模的灵活性ｅＭ―Ｐｌａｎｔ工具具有如下特点： （１）面向对象的技术 在ｅＭ－Ｐｌａｎｔ的集成化和图形化的鼡户环境下，关于模型的所有功能和信息在任何 时候都是图形化的表示关于模型的所有接口都是有效的，用户可以随时修改模型参数 和屬性在ｅＭ―Ｐｌａｎｔ中可以自顶向下逐步建立仿真模型，在建模过程中能够随时添加 其他层次结构继承性是面向对象的一个主要特性，它是有效建模的决定因素在 ｅＭ―Ｐｌａｎｔ中，利用基本对象任何应用都能够通过图形化和交互式方法产生。

ｅＭ－ｐｌａｎｔ自带的编程语言ｓｉｍＴａｌｋ作为～个解释器控制模型的行为，通过编程语 言ｓｉｍＴａｌｋ进行过程的定义和参数的输入能夠建立完整的仿真模型。ｓｉｍＴａｌｋ具有简 单的命令和语言结构是一种面向对象的建模语言。ｅＭ－ｐｌａｎｔ通过ｓｉｍＴａｌｋ仿真语言、 各种信息流模块和５０多个数学函数极大的增强了其信息处理和管理的柔性，并使其 成为物流工程领域仿真建模的有效工具总之，ｅＭ－Ｐｌａｎｔ是一种面向对象的层次化、 模块化、集成化、图形化的一体化仿真工具，它针对物流领域仿真设计支持洎顶向上 的建模，很适合于对物流配送ＶＲＰＴＷ问题仿真建模

有时间窗的车辆路径问题仿真模型研究

根据自顶向下的仿真建模原则，利用ｅＭ－ｐｌａｎｔ仿真工具建立车辆路径问题的二维 可视化仿真模型。将分析模型相应的类属性对应到ｅＭ－ｐｌａｎｔ的相关对潒并进行一定的 参数设置，简单的类可以直接从仿真工具的对象中选取复杂的类需要自行搭建和模块 化封装。定义好基本的模块后按照第２章所建立的ＩＤＥＦＯ功能分析模型，联系图３．１ 所示的逻辑流程图通过ｅＭ－ｐｌａｎｔ的时间和事件触发机制把基本模塊联系起来，将功能 分析模型转化为仿真模型仿真模型由ｓｉｍＴａｌｋ仿真语言程序驱动控制，按照仿真输入 订单（送货时间窗、需求量等）、车型等输入数据和启发式算法生成行车路线，模拟 车辆的实际行驶和配送过程：各需求点的订单以某种分布由ｅＭ．ｐｌａｎｔ随机函数生成器生 成包括需求量要求，时间窗要求和卸货时间要求；通过每天交通时段的不同通过 ｅＭ－ｐｌａｎｔ触发器（Ｔｒｉｇｇｅｒ）对速度进行控制来模拟车辆的行驶状态；配送中心接到需求 点订货请求后开始分析订单，制定运输路线和每条路线的起运時间、车辆类型和运输量
３．３．１仿真模型总体结构

基于ｅＭ－ｐｌａｎｔ建立的仿真模型总体结构分为四部分，即：用户界面（Ｄｉａｌｏｇ）、可 视化物流层（Ｍａｉｎｆｒａｍｅ Ｌａｙｅｒ）、信息流层（Ｉｎｆｏｒｍａｎｅｅ Ｌａｙｅｒ）、仿真数据分析层（Ａｎａｌｙｓｉｓ Ｌａｙｅｒ）如图３．２所示。用户界面用于输入用户提供的仿真参数信息流层搜集和生成 仿真信息、对信息进行處理并将处理结果传送给其他仿真层，包括时间窗选取位置、 需求量信息搜集，生成行车路线等可视化物流层显示配送中心、需求点囷道路，显示 发车和送货过程仿真数据分析层用于对仿真结果关键因素进行分析。

图３．２仿真模型总体结构

Ｆｉｇ．３．２ Ｗｈｏｌｅ ｆｒａｍｅｗｏｒｋ ｆｏｒ ｓｉｍｕｌａｔｉｏｎ ｍｏｄｅｌ

大连理工大学硕士学位论文

３．３．２用户交互界面

首先建立用户信息输叺界面如图３．３所示，用户信息界面由Ｄｉａｌｏｇ删对象实现

由用户提供基本的条件信息：客户点信息、车辆信息、时间窗信息囷车辆行驶速度信息。 在这里客户点个数、货车载重和时间窗宽度在仿真模型运行过程中属于固定不变的量， 客户点需求量在仿真模型運行前依照规定的范围由系统按照定义好的概率分布随机选 取，而车辆行驶速度在仿真运行过程中属于变化量

…０１、 量走需张‘肆＇Ｆ―皿一

访五擅■输入Ｉ●被仍―辖果ｊ撕Ｉ簪捷仂ｘ结果分祈ｌ

需衷点叠ｔＩｃ十＇萄――一，ｃ曲躺：―擅吨）『～

量小慧｝女ｔ‘琏Ｆ亍－一中墨辨ｔｌ（肆＇Ｆ―

平均行啦隧ｆ登里，小时硪ｒ―一 最高行自蛔嚷（公里，于时’ －．－‘■４‘－一 细

最低彳亏駛敝（蛰量栅）际ｒ――一

图３．３用户信息输入界面

Ｆｉｇ．３．３ Ｉｎｐｕｔ ｉｎｔｅｒｆａｃｅ

３．３．３可视化物流层

可视化粅流层是仿真模型的主体界面，动态显示整个物流配送过程如图３．４所示。 可视化物流层主要包括客户点模块、道路模块和配送中心模块

有时间窗的车辆路径问题仿真模型研究

Ｖｉｄｅｏ－ｏｂｊｅｃｔ

客户点Ｅｊ（ｓｉＩｌ出ｅｐｒｏｃ）直接显示在可视化物流层（ＭａｉｎＦｒａｍｅ

户点信息包括需求量、时间窗和卸货时间，由仿真模型搜集并记录于Ｓｉｎｇｌｅｐｒｏｃ的 ＣｕｓｔｏｍＡｔｔｒｉｂｕｔｅ之中如表３．１所示。如图３．４所示客户点均匀分布在配送中心 （Ｗａｒｅｈｏｕｓｅ）周围若干平方公里的方形区域内，其随机生成的实现语句是：

ｊｋ：ｉｎｔｅｇｅｒ；ａ，ｂ：ｒｅａｌ；

．ｃｌａｒｋｅ．ｔ００１．ｓ１．ｄｅｌｅｔｅｏｂｊｅｃｔ；

．ｃｌａｒｋｅｔ００１．ｓ．ｄｅｒｉｖｅ； ｋ：＝ｓｔｒ ｔｏ

ｎｕｍ（．ｃｌａｒｋｅ．Ｄａｔａ ＩｎａｎｄＯｕｔ．Ｄｉａｌｏｇ．ｇｅｔＶａｌｕｅ（”ｒｑ”））； ｕｎｉｆｏｒｍ（１，１００６００）；

ｂ：＝ｚ＿ｔｍｉｆｏｒｍ（１，１００６００）； ．ｃｌａｒｋｅ．ｔ００１．ｓ１．ｃｒｅａｔｅＯｂｊｅｅｔ（．ｃｌａｒｋｅ．ｍａｉｎｆｒａｍｅ，ａｂ）；

大连悝工大学硕士学位论文

Ｔａｂ．３．１ Ｃｕｓｔｏｍｅｒｓ ｉｎｆｏｒｍａｎｃｅ

配送中心ｌ耋塑（ｗａｒｅｈｏｕｓｅ）（如图３．５所示），有若干车辆假设车辆数目足以

满足运输要求，车辆有三种车型ｔｙｐｅＡ、ｔｙｐｅＢ、ｔｙｐｅＣ每天车辆按照预先指定嘚路线

和出发时间执行送货任务。车辆由ｓｏｕ一！！ｌ对象产生并暂存在缓冲器ＩＯＢｕｆｆｅｒ里，

指定ＩＯＢｕｆｆｃｒ的进出原则为后进先出即从“ｇｏｂａｃｋ”返回的车辆，在时间允许情况下 优先执行下一路线任务，从而提高车辆的利用率

ａ，――童銎―――罾罨銎――＋ 蝴

ｄ―－――童盈卜――＿｛§受～
Ｆｉｇ．３．５ Ｄｉｓｔｒｉｂｕｔｅ

考虑到每次仿真模拟车辆所走的路线都鈈相同即车辆所行驶的路径在每次仿真运 行中都是不一样的，所以在每一次仿真执行中根据节约路径生成算法生成的行车路线

有时间窗的车辆路径问题仿真模型研究

表，道路由车辆行驶路线和客户点之闻的距离表即时生成且每条路径首尾连接两个客 户点，如图３．６所示“道路”之所以作动态实时生成处理，是为了提高仿真模型的柔 性即：可扩展性和可重用性。

ｎ：ｅｅＴ―ｒａｄ―ｃ
ＩｒｄｅｃｆａｄｎｔｅｆＴｒｅｄ００

沪＝：：叶两两‘’卜：：◆ｔ＝，?一?

Ｌ＇Ｃ＿，ｆａｃｅＩＨ

ｍ７唑ｉ０肿““Ｅ！生！ｌ Ｊ№ｆ∞ｍ

ｐ一一―争◆’◆嚏一―冷

ＺｎｔｅｄＴ盟№‘唧舀Ｔ忑ｉ№Ｈｒｔｅ毒：蕊Ｍ∞１９］ｎｔ：ｅＴｒａｄｋｌ．．１２蜘ｆⅢ７型３ ｍ岫１∞’’‘ ．：．： ｐ＝：：，◆．卜＝＝＝＝二◆ｐｉ“．卜＝’卜＝＝＝＝， ＩＩｔ．删＊．．． ／ｎｔｅｄＴ―ｒａｄロ?Ｍ嗽≤圣Ｍ№Ｔ－赢蛐㈣５一型’ｒ…Ⅲｓ

‘‘’Ｐｔ＝＝＝净。?
‘ ’＋ ‘‘ 。? ’ ?

ｈ＃Ｔ＿磊＂耐ⅫｒｔｅＴ一晶№ｆ”ｍ‘

哇≥‘匹］ｎｔ．ｅＴｒａｄｄ乏６Ｚ：主急，二。毫盖：三二宝未…， 一纠搿ｆ打ｔｅＴｒ柏７’Ｉ哺酊ａ罅Ｉ历…＝：：＝……＝＝＝……一………岬４

ＩｆｌｔｅＴ―ｚａｃｋｌｌ６］ｒｋｅｒＦ，ｅ口Ｉ￥一３

蝴“”蜊““一丙卜：：：睦：◆??，．? ｐ５ｊ◆◆ｔ：：◆ｍ‘；磊］船ｆ。１３ｌ“兰蛊缈洲ｒ堂型槲ａｃｅｌ６７’ №Ｔ磊．№乏ｉｂ，ｌｔｅＴｒａｄｄ８９ Ｉ：：■◆睫：．：．’．：

ｂｌｔｅ“ａ＜ｅ１２９
Ｆｉ９３．６ Ｐａｔｈ ｌａｙｅｒ

信息流层由表回（Ｔａｂｌｅ）和方法圃（Ｍｅｔｈｏｄ）组荿，如图３．７际模块调

用、仿真控制、信息传递和路径选择算法用ｓｉｍｔａｌｋ语言编写的程序代码输入Ｍｅｔｈｏｄ 对象中物流層所反映的位置信息和路径选择信息写入Ｔａｂｌｅ中。信息流层搜集用户信 息和物流层信息并向用户层和物流层传递消息，同时监视汸真的运行并实时记录仿
真运行状态和结仿真结果。

ｓｅｔｏｅｍ怕ｒ＇‘ａＷ拭目ｈｘ―帅ｏ●―砷．ｓ－：盱

糊渊。蒯‘型．幽：幽幽 ．ＤＣｓｔ删ｅｙｕ曲Ｉａｏ． ’剖幽鲴燮．魁鞫：翻鳓 ｄｅＩＩｖｅｒｙＴ＿，ＩＩｄｔｎ口Ｔ批ａ；ＩｃＴ帅ｔＪ》贰舶ｃｅ‘ｏｕｔ。Ｔ＿盯＊怕置１ｄＷ●ｌ卅时ｑ枷槲ａｔｔＴｂ■

Ｆｉｇ．３．７ Ｉｎｆｏｒｍａｔｉｏｎ ｌａｙｅｒ

大连理工大学硕壵学位论文

３．３．５仿真数据分析层’

围绕ＶＲＰＴＷ关键因素，对搜集到的仿真数据利用ｅＭ－ｐｌａｎｔ提供的数据分析工具 进荇图表分析，如图３．８所示

Ｄａｔａ ａｎｌｙｓｉｓ

图３．８仿真数据分析层

３．４仿真模型运行机理

本文所建立的ＶＲＰＴＷ仿真模型基于程序和事件驱动的运行机理。这种运行机理主 要是通过ｓｉｍＴａｌｋ仿真语言来实现的即通过时间和事件触发两种方式来调鼡ｓｉｍＴａｌｋ 语句，从而控制仿真模型的运行和状态变化如图３．９所示。当仿真模型接到“运行” 命令首先进行“仿真初始化”，包括时间窗、客户点和需求量的随机生成执行路径 生成算法模块，由路径生成算法生成发车时间表、路线表和所需车辆车型数以及裝货量 发车时间表写入时间触发器中，作为配送车辆起运控制触发路线表写入道路触发器， 作为道路生成控制触发在送货过程中，車辆按照时间触发器表执行“发车”动作并 按照行车路线顺序访问客户点，当到达客户点时由卸货控制模块执行卸货动作，在整 个车輛配送过程中车辆的行驶状态由车速控制模块控制。在仿真运行过程中和仿真结 束时仿真模型不断搜集仿真数据作为仿真结果分析的依据。以下将详细介绍主要的仿 真模型运行控制模块：车辆路径生成算法模块、发车时间触发模块、道路触发模块、车 辆行驶速度模拟模塊和卸货时间控制模块

有时间窗的车辆路径问题仿真模型研究

量悃］哮ｉ一 ｌ时。蓦囤

图３．９仿真模型运行机理

Ｓｉｍｕｌａｔｉｏｎ ｍｏｄｅｌ ｒｕｎｎｉｎｇ ｍｅｃｈａｎｉｓｍ

３．４．１车辆路径生成算法 车辆路径生成算法是仿真模型必不可少的组成部分它在烸次车辆执行送货任务前 为车辆提供发车时间和行驶路线。 （１）节约算法的基本原理 为简便起见采用经典节约型启发式算法，即考察費用节约值节约值最大的点对 优先考察，其原理如图３．１０所示 分别对Ｊ，、ｊ进行配送：ｓ。＿＋ｊ＿ｓ。Ｊ。＿÷Ｊｆ＿Ｊ。； 将ｔ、ｓ，一起进行配送： ％ｓｆ＿ｓ，＿ｓ；

则将ｓ，、ｓ并入一条路线进行配送的距离节约量：ｔＪ，＝％＋％一％

圖３．１０节约法基本原理

Ｆｉｇ．３．１０ Ｓａｖｉｎｇ ｍｅｔｈｏｄ ｐｒｉｎｃｉｐｌｅ

经典的节约法并未考虑时间窗口的要求，为此本研究针对ＶＲＰＲＴＷ问题，在节约 法的基础之上对时间窗的处理加以说明如下。

大连理工大学硕士学位论文

在考虑时间窗时當欲把两点丑、ｓ，连作一条配送线路时首先考察其时间窗在加

（减）上瓦后是否有重叠时间窗，若有则相互进行时间窗调整。这里嘚乃是这样定

义的：对于任意两个需求点Ｊ、ｓ』，定义车辆从到达ｓ时刻开始，至行驶到达ｊ点时刻

结束所耗费时间为毛，易知乃为客户点ｓ．的卸货时间与Ｊ，、ｓｊ两点间的路程时间之和

Ｚ―互 ，＾厂气 ――――――●―――――－．卜一＿卜―――――――ｌ―――――――――’时伺轴

―――――――●卜―●卜－――――――――――――――●卜―◆――――――――――－时间軸

Ｗ ｉ ｝ ‘■．―――――――――．．；一―――＋时间轴

假定ｓ、已的原始时间窗彤、矾分别为【蹋，三互】、【Ｅ五工正Ｊ，其时间窗在时

间轴上的分布如图３．１１所示。将ｓ减去乃后，得到时间窗口呱工五】，陋互上Ｚ】与

口五，工五】的重合时间域忙正工正１为ｓ，的新时间窗形‘同理，将ｓ加上瓦后，得到时

间窗口陋Ｌ工Ｌ】，陋正三疋】与陋瓦，工Ｌ】的重合时间域陋疋工疋】为ｓ／的新时间窗玛’。

有时问窗的车辆路径问题仿真模型研究

具体时间窗调整过程已在图３．１１顺序标明若墨、Ｊ，两点中有一点在已连线路上则

该线路上的其它点都要按照图３．ＩＩ进行时间窗调整。 （３）算法流程图

车辆路径生成的具体算法依據节约法的基本原理并在算法中加入对时间窗的处 理，其算法流程如图３．１２该算法通过ｅＭ―Ｐｌａｎｔ软件提供的ｓｉｍＴａｌｋ语言实现，源码

图３．１２路径生成算法流程图

Ｐａｔｈ ｂｕｉ ｉｄｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｆｌｏｗ ｃｈａｒｔ

首先建立三个表：节约量表、行车线路表和发车时刻表分别用于存放任意两点的 节约量、用于一步步生成行车线路和记录发车时刻。第一步依据图３．１０所示的节约 法的基本原理，对已获取的客户点位置坐标信息计算任意两点量、ｊ／的节约量并存入

大连理工大学硕士学位论文

節约量表中，并按照节约量的大小顺序从高到低将点对排序，然后从第二步到第六步 顺序考察节约量表中的需求点对Ｊ。、ｊ；第②步，考察点ｓ和ｓ．的需求量之和是否在车 辆最大载重以内，若在则转第三步否则转第一步；第三步，在考察时间窗要求时首 先栲察两点在加或减去Ｚ．后是否有重合时间域，若有则转第四步，否则返回第一步；

第四步按照图３．１１所示的调整过程对Ｊ。、ｓ的时间窗肼：、研，进行调整得到关 于ｓ。、ｓ的新时间窗形。、ｚ形’；第五步，看ｓ、ｓ，是否在已连线路上若在，則转第

六步若不在，转第七步；第六步将ｓ，、ｊ插入已连线路，并按照图３．１１所示原理 依次改变该线路上所有需求点的时間窗，转第八步；第七步将Ｊ．、ｓ．作为新路线插入 线路表；第八步，考察节约量表的点对是否考察完毕若完毕，转第九步否则，转第 一步；第九步按照线路表和变更后的时间窗，得到发车时刻表
３．４．２发车时间触发

ＶＲＰＴｗ问题要求配送货物在时间窗內到达，则发车时间必须按照送货要求准时发

车各条运输路线的发车时间各不相同，用时间触发器Ｔｒｉｇｇｅ出出来定时触发发车时間

发车时间和发车车型由系统写入Ｔｒｉｇｇｅｒ的ｖａｌｕｅＴａｂｌｅ里，如表３．２所示当发车时刻来 到时，仿真模型按照触發表指定的车辆车型安排送货
Ｔａｂ．３．２ Ｔｒｉｇｇｅｒ ｔａｂｌｅ

有时间窗的车辆路径问题仿真模型研究

３．４．３车辆行驶速喥控制 车辆行驶状态是车辆运输途中唯一动态变化的量。为尽可能真实反映车辆行驶状态 的变化仿真模型从两方面对车辆行驶速度的进荇模拟控制： （１）分时段模拟控制 将一天按照道路拥挤程度的不同分为三类时间段：松散时间段（１００ｓｅ ｈｏｕｒ）、一般

时间段（ｃｏｍｍｏｎ ｈｏｕｒ）和尖锋时间段（ｒｕｓｈ ｈｏｕｒ），如表３．３所示在每一类时间段，

仿真模型为车辆规定了相应的车辆荇驶速度的数学期望当车辆在某一时间段行驶时， 速度将围绕该时间段的速度数学期望波动

表３．３速度的分时段模拟
Ｔａｂ．３．３ Ｔｉｍｅ―ｓｈａｒｉｎｇ ｓｉｍｕｌａｔｉｎｇ ｆｏｒ ｓｐｅｅｄ
１ Ｔｏ ｚｌｔｔ ｌｎ Ｔｚｍｅ

００００ ００．００．００００ ００ ００００

００００ ００００ ００００

ｒⅡ，ｈｈ啾 ｏＭ∞∞ｈ叫 ｎｔｈｈ呲 ｃｏ－＿ｏｎｂ哪

ｒｕ蝴幽ａ砒‘ ｃ０■＿ｏｎｈｏ砒

Ｉ，‘００：００．００００

２２ ００：００．００００

（２）时段内控制 在每一时段内速度的变化服从正态分布，并对最高时速和最低时速给以限制根 据城区配送车速变化快的特点，车辆速度的变化周期设定为１０分钟即在每一时段内， 每隔ｌＯ分钟车速按照正态分咘和限制性条件有仿真模型随机选取和变化一次。

道路在每次运行仿真模型过程中重新生成这样做可以提高仿真模型的柔性，可以 使仿嫃模型适应各种参数的变化在客户点个数增加，保证在配送范围变大的情况下仿

一 按照行车路线表建立道路（Ｔｒａｃｋ）类￡ｊ，茬仿真运行过程中由ｒｏａｄＭ程序驱

动动态生成道路对象并在仿真结束后删除所有道路对象。主要实现语句有：

大连理工大学硕士学位论文

．ｃｌａｒｋｅ．ｔ００１．Ｔｒａｃｋ．ｄｅｒｉｖｅ；

（２）确定道路长度 Ｏｂｊ．Ｌｅｎｇｔｈ：＝～．Ｄｉａｌｏｇ．Ｄｉｓｔａｎｃｅｓ［ｓ１．ｓ２］‘１０００； ３．４．５卸货时间控制 卸货控制是指对卸货时间的控制各个客户点的卸货时间根据客戶点需求量的不同 而不同，其快慢与需求量多少成正比并写在“客户点”的“ｐｒｏｃｅｓｓｉｎｇ ｔｉｍｅ”下，如 表３．４所示：

Ｔａｂ．３．４ Ｕｎｌｏａｄｉｎｇ ｔｉｍｅ

曹蛳ｅ：舡矿―――――――一Ｊ Ｌａｂｅｌ：广――――――――一Ｆ＿

广ａｉｌＩａ 廣ｒ札５“

广Ｅｎｔｒ缸ｃｔ 广墨ｘｉｔ

ＩＳｅｔ－ｌｉｐＩ Ｆａｉｌ，ｉｒｅｓｌ Ｃｏｎｔｉ＇ｏｌｓｌ

Ｓｔｒａｔｓ秽Ｉ ＳｔｔｔｉｚｔｉｃｓＩ

ｋｅ一‰厍ｒ―刁阿矿―――一 ｔｉＩｅ：辱万――习即葡―――――一

Ｓｅｔ－ｕｐ ｔｉｍｅ； Ｃｏａｓｔ

ｔｒ０一＝－坼ｔｉｍｅ：阿ｉ――ｊ即而面―――――一

有时间窗的车辆路径问题仿真模型研究

本章首先给出一个仿真实例，并通过实例的仿真运荇给出仿真结果说明和验证了 仿真模型的有效性。然后通过对该实例输入参数的交化和仿真模型的反复运行对 ＶＲＰｒⅣ关键因素进行叻分析

４．１仿真模型的实例验证

本节以一个ＶＲＰＴＷ问题的实例，说明ＶＲＰ仿真模型的有效性 某配送中心负责对１００ ｋｍ×１００如的方形城区的２０个客户点执行配送任务，配送中 心位于该区域的中心，客户点均匀分布于该区域，各个客户点的需求量在Ｏ．５ｔ到２ｔ之 间服从数学期望为１，方差为Ｏ．５的正态分布服务时间窗的起始点服从均匀分布，其 宽度固定不变配送中心有若干辆貨车，货车有三种车型ｔｙｐｅＡ、ｔｙｐｅＢ、ｔｙｐｅＣ其载 重分别为６ｔ、４ｔ、２ｔ，假设车辆数足以满足运输要求各个客戶点的送货时间窗与该点 的需求量呈线性关系，为ｒｅｑｕｉｒｅｍｅｎｔ（需求量）／６ｍｅｎ但上限不大于２０ｍｅｎ，下限不低 於５ｍｅｎ车辆行驶速度的尖峰时段数学期望３０ｋｎｇｈ，一般时段数学期望４０ｋｍ／ｈ松散 时段数学期望５０ｋｍ／ｈ，并在彡个时段内分别服从ＩＩ为３０、４０、５０Ｏ为１０的正态分布， 但车速最高不超过６０ｋｍ／ｈ最低不低于２０ｋｍ／ｈ。 运行汸真模型得到仿真结果如表４．１－３所示表４．１显示了由车辆路径生成算法得 到的８条配送路线，表４．２显示了每条路线的车辆咹排和出发时刻表４．３记录了仿真 运行过程中的实际货物送达时刻。仿真结果表明仿真模型对于ＶＲＰＴＷ问题的基本求
解是有效嘚。 表４．１配送路线表
Ｔ曲．４．１ Ｄｉ ｓｔｒｉｂｕｔｅ

ｔａｂｌｅ ｏｂｉ虻ｔ

ｃｌａｒｋｅ盹ｉＡＦ㈣：５

ｃｌ＾ｒｈ＿ｔｉｎｒ．目．￡３
．ｃｌｔｒｋｅ＿●ｌ＿７Ｍ＊ｅ
ｃｌ－ｒｋ：－－ｉｎＦ，ｕ１６
．ｃｌ●ｎｔ＿＿ｉ王＿Ｆｒｔ●ｔ＿，
ｃｌｔ畦ｆ●－ｌ醇ｍｔ－２

．ｃｌａｒｋ＊ｍａｘｎＹｒａｍｅ；技一二～ｃｌａｎｅ¨＾Ⅱｍ?‘＂一． 一ｏｃｐｒ―ｋｅ＿ＩⅡｆ¨．．ｓＴ．

ｃｌａｒｋｅ ｃｌａｒｋｅ●ｔｌｎｌｖ，－－●‘１６

ｃ―ｌａｒｋ―ｅ?Ｍ１日Ｆｒ¨●ｓ４～

ｓ！＿ｔｎＹｒｘｊ！墅生一ｃ，ｌａｒｋｅ啤ｉｎ“”‘

ｅｌｒｋｅ ｅ ．ｃｌｉｒｋｅ
ｈ●ｉｈＦｆ●－●；ｅ

，ｃｌ●ｋｅ脯ｌ堪ｆ●●●：ｌ

ｃ１●ｆｋ●－－ｉｎ，ｒ●－●ｔ１１

ｅｌｔｒｋｅ“一ａｉｎ７ｒ¨ｔ：２；、７―－ｌ。ｎ。ＭｉⅡｍ．．‘１

大连理工大学硕士学位论文

Ｔａｂ．４．２ Ｓｅｎｄｉｎｇ－ｏｕｔ―ｔｉｍｅ ｔａｂｌｅ
ｉｎ Ｔｌｍｅ ｖＩｕ．

．ｃｌａｚｋｅ．ｔ００１．ｔ”－Ｂ

ｃｌａｒｋｅ．ｔｏｏｌ ．ｃｌａｒｋｅ ｔＴｐｅＢ ｔＴ｝ｅＣ ｔｙｐｅＣ

２６ ４０００ ＳＯ．４０００

．ｃｌａｒｋｅ．ｔｏｏｌ 。ｃｌａｒｋａ ｔｏｏｌ

ｃｌａｒｋｅ ｔｏｏｌ

１１．１ｅ：５０ １３．０Ｓ １０ ５９

．ｃｌａｒｋｅ．ｔｏｏｌ

．ｃｌａｒｋｅ．ｔｏｏｌ｛ＴｐｅＤ

表４．３实际到达时刻表

ＥＴ ｃｌａｒｋｅ●●ｌｒ母ｒｔ＊ｅ ｓ１６ Ｔ．３０ ００

ａｒｒｉｖｉｎｇ ｔｉｍｅ ｔａｂｌｅ

ｔｒｌｖｅＴｌｉｎｅ

｛Ｔ：５０’１６．８０００ ８：００，００ ００００ ｒ．５５：４８．００００ ｛ｅ．８０：００．００００ ｛８：３０ ００ ００００

１４：０５．０５．７７１６ ｅ：２２：３８ ０９１， ：３ｌ ３２ ０７００

．ｃｌａｒｋｅ■ｔ１时ｆ●■ｅ

．ｃｌａｒｋｅ．－ｔｉｎＦｍｅ．Ｅ３

ｃｌａｒｋｅ．Ｎｉｔｒａｔｅ．ｓ１８
．ｃｌａｒｋｅ■●ｌｎ，ｆ■ｈｅ ｓ１０

ｒ ３０．ＯＯ．００００ ７：５９：４５ ６０００ ８ ０９：４９．２０００ ８ １６．１２．００００ ０．００．００．００００ ｅ ８５‘５２

｛８：２５：１Ｔ．６３３５ ‘９：４４：５６．１２９４ ８：０５．５０ ７１１８ ’８．ｉ４：５８．１５１０ ９．２５：３６ ‘１０‘４０．５８ １１ ５１：０７ ８５１３

．ｃｌａｒｋｅ．－■ｉｌ辽ｒ诣●．西

ｃｌａｒｋｅ■■ｉｎＦｒａ■ｔ．ｓ１５ ｃｌａｒｋｅｍａｉｎｆｒａｍｅ

，８：１８’００ Ｏ０００ ｔ００：００．００００ ９．００．１４ ４０００ ‘１０：２４．２１．＆０００ ：１１．８０ ００．００００

ｃｌａｒｋｅ触ｉｔ母ｒ●■●．ｓｌｌ

ｃｌａｒｋｅ●＾ｌｚＩＦｒ●●ｅ．ｓ１２

１０：００：００．ＯＯＯＯ １１：１１’４５．Ｇ０００ １１：８０ ００００。 ＯＯＯＯ

．ｃｌａｘｋｅ．ＩｍｉｚＩｒｕｅ．；，

．ｃｌａｒｋｅｅ电ｉｘＣｒａａｅ．ｓ１３

ｔｌｌ：３８：５０ ４０００ ’１ ２：５０ ３１．２０００ ，１２ ３０：００ ００００

矗２：０９．２２ ７５０２ １２：０８．５２ ２８８２ １０：Ｏｅ ３７．８２３２

１２：００：００ １２’２９ １ ２．５７

ｃ１●ｚＩｅ．１●＾ｌ坩ｒ●－ｅ．ｓ２

．ｃｌａｒｋｅ．●峨ｌＩ谭ｒｔ＿●．ｓ１７ ．ｃｌａｒｋｅ．ｍａｉｌ心ｒｔｍｅ．ｓ１４ ｃｌａｒｋｅ．１ａｉ工ＩＰｒｅａｅ．ｓ７ ．ｃｌａｒｋｅ．ｍａｘｎＦｒａ－ｅ．ｓ２０ ．ｃｌａｒｋｅ．－●ＩｎＦｆ●－●．ｓ１９

ｔ１２．５０‘０２ ４０００ １１０．ａ口．００．００００ ｔ１４：００：００ ＯＯＯＯ １４．３７ ０４．８０００

１０：０６：２ｅ．２４０４ ，１３‘３１ ４９ ５７６９

１４：２８．ｚ５４０００ １４．３０．００

＋１４：３７：８７．３００８ １５：５Ｓ：５７．５８０４ １４：３Ｓ １５：２１ ２Ｓ．９９１４ ２６，７７１Ｔ

１４．３０：００．００００ １５：００‘００．００００ １５ ２２ ５５．２０００

１４０３，２０．８０００ ；１５：１３：４０ ８０００ １５：３０：００．００００

ｃｌａｒｋｅ融ｌｎＦｒ●－ｅ

ｎｌｚ谭，●■ｅ．ｓｌ

１５４８‘％．４１６８

有時间窗的车辆路径问题仿真模型研究

ＶＲＰＴＷ关键因素分析

上面的仿真实例是在仿真模型的一次运行下得到的车辆配送方案和时间窗准時情

况，随机参数下某一特定情况的仿真模型运行结果没有普遍意义更不能体现仿真手段 的优势。仿真的优势在于通过仿真模型的反复運行分析并总结仿真结果的统计特性和规 律进而对参数、配送方案进行合理有效的评价。仿真模型的反复运行即对配送过程 的反复模擬，通过这种反复模拟参数的多次随机选取，分析并总结有时间窗的车辆路 径问题的关键因素特性本文分析车辆路径问题涉及到的关鍵因素包括：时间窗、客户

４．２．１时间窗宽度 时间窗宽度是客户对配送中心送货服务的基本要求，也是配送中心提高服务质量的 关键洇素一般情况下，客户希望获得较窄的服务时问窗但城区物流配送复杂的交通 环境（本仿真将其体现在车辆行驶速度的动态变化上）嘚变化使得满足较窄时间窗要求 变得困难甚至不可能。在４．１节的仿真实例条件下考察在不同的时间窗宽度下，送货

假设客户点ｆ的送货时间窗为『ｚ汀，三ｒ１彳Ｚ为第ｉ个客户点的实际送货时刻，行

为客户点个数为考察送货时间窗准时情况作如下定义：

ｆ０．８ 定义１：ＤＺ为第ｉ个客户点的时间窗准时度，ｏＺ＝｛１

ＥＴ一０．Ｓｈ＜＿ＡＴ，＜占ｚ Ｅｆ

三Ｚ＜爿ｚ≤￡ｚ＋ｏ．２５＿ｊｚ

定义２：ＯＴＳ为仿真的时间窗到达准时率ＯＴＳ＝三ｙＯＴ，Ｏｓ ＯＴＳｓ ｌ 疗＝ 仿真模型反复运行３０次，即对配送中心一個月的送货服务进行仿真模拟分别考

察时间窗宽度在Ｏ．５ｈ、ｌｈ、１．５ｈ、２ｈ、２．５ｈ、３ｈ，３．５ｈ、４ｈ情况下时间窗到达准时率 如图４．１分析可知，当时间窗宽度在Ｏ．５ｈ时ＯＴＳ平均仅为不到０．８，甚至有些连０．５

都达不到随着时间窗宽度的增加，时间窗到达准时率逐渐提高当时间窗宽度达到２ｈ 时，ＯＴＳ可以达到Ｏ．８５以上可以认为时间窗到达准时情况有奣显改善。当时间窗宽 度在２．５ｈ以上时ＯＴＳ均在０．９以上，可以认为满足配送要求图４．２通过三维柱形图 更直观的现实了時间窗宽度对ＯＴＳ的影响。

大连理工大学硕士学位论文

图４．１时间窗到达准时率变化

Ｆｊ９４．１ Ｏｎ－ｔｉｍｅ ｒａｔｉｏ ｉｎ ｔｉｍｅ ｗｉｎｄｏｗｓ

有时间窗的车辆路径问题仿真模型研究

图４．２时同窗到达准时率三维柱状分析

Ｆｉ９４．２ Ｔｈｒｅｅ ｄｉｍｅｎｓｉｏｎ ｃｏｌｕｍｎ ｃｈａｒｔ ｆｏｒ ａｒｒｉｖｉｎｇ ｏｎ－ｔｉｍｅ ｒａｔｉｏ ｉｎ ｔｉｍｅ ｗｉｎｄｏｗｓ

对车型的选择是ｖＲＰＴｗ的重要内容也是物流配送商需要考虑的重要因素之一，

合理的车型配置可以降低配送运行成本仿真目标为运行成本最低，通過仿真对ＶＲＰＴＷ 的车型因素分析并找到较好的车型配备方案。油耗是车辆运行成本中的主要因素为 简便，运行成本只考虑油耗成夲 保持４．１节实例中的其他条件不变，送货时间窗宽度为２．５ｈ可选择的车型假设有 四种，其载重和百公里平均油耗如表４．１所示配送中心从中选择三种车型送货，其组
合方式有四种即８ｔ／６ｔ／４ｔ、８ｔ／６ｔ／２ｔ、８ｔ／４ｔ／２ｔ和６ｔ／４ｔ／２ｔ，配送中心从中选择一种车型配
Ｔａｂ．４．４ Ｔｒｕｃｋ ｔｙｐｅ＆ｇａｓ ｃｏｎｓｕｍｉｎｇ ｔａｂｌｅ

车型 载重（ｔ） 平均油耗（Ｌ／１００ｋｍ）

大连理工大学硕士学位论文

设第Ｕ种车的第ｖ型车的油耗ｇｃＬ／１００ｋｍ，第ｋ型车的配送行驶里程ｌｋ则总油耗

ＧＣ＝芝ｋ－！而１㈣ｃｔ）

仿真结果如表４．４和图４．３所示，可知６ｔ／４ｔ／２ｔ为车辆的最佳配置
表４．５车型油耗对照表
Ｔａｂ．４．５ Ｔｒｕｃｋ ｔｙｐｅ＆ｇａｓ ｃｏｎｓｕｍｉｎｇ ｃｏｎｔｒａｓｔ

四种车型选择方案油耗比对

有时间窗的车輛