基于聚类分析和遗传算法的带时间窗车辆路径问题研究.doc

福建农林大学硕士学位论文基于聚类分析和遗传算法的带时间窗车辆路径问题研究姓名：林郁丞申请学位级别：硕士专业：交通运输规划与管理指导教师：张正雄20090401基于聚类分析和遗传算法的带时间窗车辆路径问题研究：（），（），埘，”，”，冲；，福建农林大学届硕士学位论文，：；：独创性声明本人声明，所呈交的学位（毕业）论文，是本人在指导教师的指导下独立完成的研究成果，并且是自己撰写的。尽我所知，除了文中作了标注和致谢中已作了答谢的地方外，论文中不包含其他人发表或撰写过的研究成果。与我一同对本研究做出贡献的同志，都在论文中作了明确的说明并表示了谢意，如被查有侵犯他人知识产权的行为，由本人承担应有的责任。学位论文作者亲笔躲科如矽。乡哆论文使用授权的说明本人完全了解福建农林大学有关保留、使用学位（毕业）论文的规定，即学校有权送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。保密，在年后解密可适用本授权书。口不保密，本论文属于不保密。口学位（毕业）论文作者亲笔签名指剥币亲笔签名：；苏汐诹唧显嗍蹿。夕日凝：抛福建农林大学届硕士学位论文绪论研究背景随着我国经济的高速增长，当前物流活动呈现出前所未有的频繁，年月份，全国货物运输量较上年同期增长，货物周转量较上年增长。、三个月的增速不仅没有下降，而且增幅持续上升，增幅分别为、，预计年公路运输车辆市场依然稳定并将保持上升态势【】。但是目前我国物流管理仍然比较落后，物流行业普遍面临着专业化程度低、高耗低效等问题。另外，随着新世纪的到来，电子商务的蓬勃发展，市场竞争进步加剧，企业要保有和争得市场，不仅要在产品的质量、功能上下功夫，更重要的还是要在优质服务上下功夫。据统计我国车辆的运输成本是欧洲或美国的倍，全国运输汽车的空驶率约，其中汽车物流企业车辆空驶率达，存在着回程空驶、资源浪费、运输成本高等问题【】。可见，减少运输费用是有效减少物流成本的重要方面。对于物流中心和第三方物流企业的货物配送，运输车辆调度和线路优化是工作的重点，正确合理的调度可以有效减少车辆的空驶率，实现合理路径运输，从而有效减少运输成本，节约运输时间，提高经济效益。车辆路径问题（，缩写为）【是物流配送过程中的关键问题之一，该问题作为网络优化的基本问题之一而一直受到学者们的关注。一般指对一系列的客户点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、车辆容量限制和时间窗限制等）下，达到一定的目标（如运距最短、费用最少、车辆数尽量少和客户满意度最佳等）。的研究作为发展敏捷后勤的一个重要组成部分，是实现物流现代化的基础和前提条件，不仅有助于改变我国物流管理落后的现状，也有助于解决城市交通拥挤、能源短缺、大气污染等困扰人们的社会问题，实现效率、资源、环境和价值观念各方面的内在统一，促进物流业的进步和社会经济的可持续发展。随着社会经济的不断发展，人们对物流配送的实效性要求越来越高，对配送时间提出了明确要求，一般都规定了一个希望被访问的时问窗，要求在此时间窗内接受服务，这就产生了有时间窗的车辆路径问题（基于聚类分析和遗传算法的带时间窗车辆路径问题研究，缩写为），它是在的基础上增加了客户要求访问的时间窗约束。这就对物流配送技术提出了新的挑战。随着物流配送行业竞争日益激烈和客户对物流配送时效性要求越来越高，对的研究，尤其是对的研究，不仅可以帮助运输企业提高服务水平，为顾客提供快捷、准时、安全、舒适的服务，解决发展电子商务中速递这一“瓶颈”约束，而且有助于企业节约运输成本，改善车辆利用效率，缩短生产周期，加速资金周转，实现资源的合理配置，汲取“第三利润源泉”的财富，因此更加具有实际意义。国内外研究现状车辆路径问题最早是由和于年提出的，一般定义为：对一系列装货点和（或）卸货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件下（如货物需求量、发送量、交货时间、车辆容量限制、行驶里程限制、时间限制等）一卜，达到一定目标（如路程最短、费用最少、时间尽量少、使用车辆数尽量少等）。由于其应用的广泛性和经济上的重大价值，一直受到国内外学者的广泛关注。在经典的基础上，车辆路径问题在学术研究和实际应用上产生了许多不同的延伸和变化型态，包括旅行商问题（，）（可看作的一个特例，即当只包括一条路径，且没有能力约束）、带能力约束的车辆路径问题（，）、带时间窗的车辆路径问题（，）、追求最佳服务时间的车辆路径问题（，）、多车种车辆路径问题（，）、车辆多次使用的车辆路径问题（，）、考虑收集的车辆路径问题（，）、随机需求车辆路径问题（，）、动态车辆路径问题（，）、满载非满载、双向等】。车辆路径问题的求解方法主要足精确算法（如分枝定界法、切平面法、动态规划法）和启发式算法（详见图）。福建农林大学届硕士学位论文生辆路径问题的求解方法图车辆路径问题的求解方法国外研究现状经典可描述如下：有多个货物需求点（或称顾客），已知每个需求点的需求量及位置，至多用辆汽车从配送中心（或中心仓库）送货，每辆汽车载重量一定，安排汽车路线，要求每条路线不超过车辆载重量和每个需求点的需求蓟叟舭搬法翩裣法法索火络法近法法类弼算算搜退网间内断法样觯法法施觥就黜法黜舫黻黻一一一捌一蝴撇鼾眺赫瑚。厂、基于聚类分析和遗传算法的带时间窗车辆路径问题研究必须且只能有辆车来满足，目标是使配送距离或者配送费用最少。年，等人【首先提出冲的集分割，直接考虑可行解集合，在此基础上进行优化，建立了简单的模型。年，等人【】提出将动态规划法用于固定车辆数的，通过递归方法求解，可以求得最优解，但计算时间过长且占用内存量大，由于其计算量随变量的增加成指数倍增长。提出了状态空间松弛，极大地减少了状态数量。年，等人【】提出算法（扫描法）求解，此方法扫描每一个点，速度慢，且只适用于小规模问题的。年，等人】提出了度中心树和相关算法，对固定车辆数的进行度中心树松弛。后来，【】对改该算法进行改进，可求解有个客户的。等人【】将禁忌搜索方法应用于，该算法求解的领域，是通过过程得到的。它针对比较好的肩发式算法，可以成功地应用于许多经典的，但该方法可能搜索到局部最优解。其后等人【通过按角度和路径重心对原问题的空间进行分割，再用禁忌搜索结合模拟退火对子问题求解，实现了对问题求解的并行化。年，】将遗传算法用于的研究，并可有效求解带时间窗的。鉴于传统的遗传算法是个大范围、粗粒度的寻优算法，一】将其与约束满足问题（）的技术相结合，通过遗传算法来处理参数的子域（基因的适应度通过解的计算得到），从而减小搜索空间，降低问题目标函数和遗传算法约束的复杂度。在国外，大批学者也对带时间窗车辆路径问题（）进行深入的研究。年，和提出算法（成本节约法），等人通过使用适当的数据结构，降低了它的复杂度，法随后成为许多专家和学者研究的基础，但该算法求出的解是较优的可行解，不一定是最优解。年，等人】在的集分割的基础上引入生成法进行求解，这种算法本质上是最短路径算法，同时结合了分枝定界算法，曾用它求解了有个客户的，但计算时间长且由于计算量过于庞大导致内存使用常有不足现象发牛。年等人【针对带能力约束、时间窗口以及无停留时间的，提出了三下标车辆流方程。年，】和，分别用遗传算法求解了，但是都存在“早熟收敛”的问题。福建农林大学届硕士学位论文年，和】提出了一种基于贪婪算法（）的来求解，该算法使用贪婪算法构造可行路线，然后使用规划各个顾客的访问顺序，其中的编码方式是用顾客的索引顺序来编码，遗传算子根据顾客的全局优先关系进行设计。年，等人【捌提出了重复匹配的方法，该算法在其模型里同时考虑了时间约束和能力约束，因此适用于这类具有强约束的，另外，重复匹配算法也可求解较大规模的。年，提出一种基于的系统用于，该方法是一个两阶段法，它使用了先聚类后规划（，）的方式，结合了局部优化算法和遗传算法。该混合算法首先使用将有需求的顾客进行划分，即把顾客分配给各个服务顾客的车辆，这一过程就是所谓的“遗传聚类（）”，每一个聚类都对应于一个用于服务顾客的车辆。在聚类过程完成后，对每一个聚类（即每一辆车）使用启发式算法来规划该聚类中的顾客服务顺序，然后使用算法对所得到的解进行邻域搜索，从而将路线优化。在使用系统解决时，由于遗传聚类要首先确定其初始聚类数目，所以需要预先知道用于服务的车辆数目，而且使用遗传聚类只能优化车辆的行驶时间，而不能优化所用的车辆数目。以上两种算法属于比较典型的传统混合遗传算法。年，等人将神经网络和结合使用来求解，其使用竞争神经网络（）选取顾客，利用改进的插入法来安排顾客顺序。在使用这种改进的并行插入算法时，需要三个参数。、“，其中前两个参数用于权衡时问因素和行驶路程因素，用于控制插入时的节约量，而则用于进化由并行插入算法得到的初始路线。年，等人【】将与路径构建启发式算法相结合，在遗传编码过程中忽略了编码问题而采用一组可行的路线表达一个解。在此基础上，等人于年改进了该算法：同时进化两个种群，其中一个种群用于优化车辆行驶的总路程，另一个种群用于优化时间窗冲突算法的初始化基于随机顺序插入法改进了两种交叉算子和六种变异算子。等人的一系列改进为我们研究采用混合遗传算法解决开拓了思路，从中可以了解到如何构造混合遗传算法中的各种遗传算子，以设计用来解决的新方法。年等人提出一种（）系统用来解决，其以蚁群算法为基基于聚类分析和遗传算法的带时间窗车辆路径问题研究础，主要设计用来解决个目标函数的，个是使车辆数最小，另一个是使时间最短，而最主要的目标是使时间最短，该算法只在总体上优于其他算法，求解具体问题时优势不是很明显。年，】混合使用了、基于局部搜索（）的演化算法（）以及路径构造启发式（）算法，并运用了两阶段法的思想：第一阶段，用获得可行解第二阶段，使用演化算法进行演化，从而得到优化的解。该方法与以前算法的不同之处在于，使用了随机启发式算法初始化以及基于最大邻居搜索（，的交叉运算和变异运算。年，等人【】提出了一种针对的混合遗传算法，该算法采用一般的序数编码方法，运用了启发式的交叉操作、自适应的变异机制以及混合爬山方法等一些高级技术，对的个实例测试后，获得了较好的解。年，等人【】提出了一种基于和禁忌搜索的混合遗传算法，其用优化车辆使用数，用禁忌搜索算法优化车辆行使距离，仿真结果优子各单一算法的求解。年，等人】对不确定车辆数的进行了改进的遗传算法优化，取得了较为理想的效果。年，等人【提出混合最优法的混合遗传算法，设计出专门遗传算子和长度可变的染色体，最大限度地实现了的多目标优化。国内研究现状在我国，遗传算法、改进遗传算法以及启发式算法被国内学者们广泛的利用。年，姜大立等人【】在分析现有启发式算法的基础上，构造了的染色体表达，并对染色体进行可行化影射，建立了的遗传算法。可以有效求得最优解或近似最优解。张涛等人【】则通过遗传算法来保证搜索的全局性，用算法来加强局部搜索能力，等到针对的混合算法。这类算法目前已可以求解较大规模的问题（个客户）。年，肖鹏等人】通过构造的染色体表达，采用基因换位算子进行染色体重组，实现了新颖的单亲遗传算法。年，李嘉等人【】通过引入“车队模式”，提出了混合车队的求解框架，设计了基于遗传算法和禁忌搜索启发式的混合算法。年，张丽萍等人】通过引入新颖交叉算子，构造了一种改进遗传算法，此算法摆脱了对群体多样性的要求，不存在传统遗传算法常见的“早熟收敛”问题，可以有效求得的最优解。纪寿文等人【根据深圳市科技园的实际路网图，采用神经网络的方法对运输车辆优化调度进行了试验研究，但神经网络需要较多的数据，在数据缺乏的情福建农林大学届硕士学位论文况下不适合应用神经网络对供应商进行选择。年，方霞等人】利用免疫算法的全局搜索能力和收敛性，将新型的启发式算法用于解决。王正彬等人在分析现有启发式算法的基础上，建立了考虑线路安排的物流配送方案模型，并提出了求解该问题的一种搜索算法。黄岚等人通过引入交换子和交换序的概念，构造出一种特殊的粒子群优化算法求解旅行商问题；年，陈湘州等人【】引入种进化逆转算子，改进了遗传算法求解时的局部搜索能力。顾志康等人【】针对染色体中某些需求点编号可能重复出现的情况，设计新的染色体结构，并通过基因的混合交叉方法进行基因重组，有效提高了搜索到最优配送路径的概率。此外，崔雪丽等人【】基于近些年出现的新型智能优化思想：人工蚂蚁系统，给出了一种可快速求解的蚂蚁搜索算法。通过定义基本的人工蚂蚁状态转移概率，并结合局部搜索策略，用迭代次数控制算法的运行时间，从而使该方法具有实用意义和可操作性。经一系列数据测试和验证，并与若干已有的经典算法相比较，获得了较好的结果，但该算法需要不断调整变量，需要较长的搜索时间，容易出现早熟停滞现象。章兢等人删构造了一种免疫克隆算法来求解，并在算法中引入了克隆选择、克隆删除、受体编辑、体细胞高频变异、抗体循环补充等思想。仿真计算结果表明，免疫克隆算法能快速收敛于全局最优解，克服了遗传算法中易陷入局部最优解和收敛速度慢的缺点，可有效地解决物流配送车辆路径优化问题。年，肖健梅等人【】设计了一种新的实数编码方案将车辆路径问题转化成准连续优化问题，并采用罚函数法处理约束条件，从而把微粒群算法应用于车辆路径问题的求解，但存在容易陷入局部最优的缺陷。年，曹剑东等】针对北京市内货物配送和收集这一典型的问题，在算法结合算法计算距离矩阵的基础上，以混合禁忌搜索算法为理论基础进行静态调度求解，并以局部调整策略实现的动态调度计算，开发基于技术的动态车辆调度系统。该研究将算法和算法有机结合，提高了整个寻路算法的执行效率；此外，基于技术开发的动态车辆调度系统，能够满足调度人员实时准确的调度需求，对降低配送和集货成本具有重要意义。在带时间窗车辆路径问题方面，国内学者也进行大量的研究。年，李大卫等人对适用于旅行商问题的最近距离搜索启发式算法进行修正，构造出评价基于聚类分析和遗传算法的带时间窗车辆路径问题研究函数，并据此提出一个求解的启发式算法。年，谢秉磊等人【】将货运量约束和时间窗约束转化为目标约束，设计了基于自然数编码的可同时处理有软、硬时间窗的遗传算法（），得到了较好的结果。年，周贤伟等人【】根据车辆装载设备的特性，建立了的数学模型，设计了相应的。年，宋厚冰等【】针对，在标准的基础上，将分组信息与每一个染色体结合，并辅以交换局部搜索技术，构造了一种，使得求解结果更接近最优解。宾松等】用一种新的编码方法及交叉和变异概率的自适应机制，构造了改进的求解。丁建立等人【】融合了遗传算法与蚂蚁算法，采用遗传算法生成信息素分布，利用蚂蚁算法求精确解，对的简单形式一旅行商问题进行了仿真，取得了非常好的效果，但存在如计算时间较长，容易陷入局部最优等问题。年，吴璩莉等人】采取将禁忌搜索作为变异操作的混合策略，将禁忌搜索算法和融合求解，其性能优于简单的。刘小兰等人阻为了克服原有大规模邻域搜索算法不能有效求解时问窗较宽的缺陷，介绍了的通用数学模型，并通过分析各主要变量之间的关系，设计了一种简单、快速的确定性初始算法，同时引入“短路径优先策略”构造了改进的大规模邻域搜索算法，该策略也可嵌入到求解时间窗比较窄中，达到加速搜索的目的。年，刘诚等人蝌对在求解时初始种群的单一性，提出一种并行遗传算法，该算法对不同的种群用不同的初始化方法一随机初始化法和构造初始化法，效果比较理想。杨明等【】针对有时问窗的车辆路径问题，在标准的基础上，加入爬山算法增强了算法的局部搜索能力，通过保护全局最优基因的方法提高了算法的收敛能力，并辅以自适应变异算子，构造了一种改进的混合遗传算法，实验结果表明，改进后的算法具有抗“早熟”能力强、收敛速度快和局部搜索能力高的特点。年，杨宇栋等】引入客户直接排列的解的表示方法，改进了模拟退火算法，提高了求解的效率。从理论上讲，用模拟退火法求解，可以求得全局最优解，但在实际应用中，由于受计算时间的限制，往往只能给出一个近似的最优解，为了使模拟退火算法求出的近似解更准确，一般重复执行模拟退火法多次，从中选取最好的解作为最终的近似最优解。张海刚等【】研究了基于改进免疫遗传算法的带硬时问窗车辆调度问题的实现，并对算法的信息熵计算加以改进。这种算法简单可行，提高了优化算法的质量和搜索效率并福建农林大学届硕士学位论文能够在较短的世代数内快速地收敛到全局最优解，显著提高了算法的全局收敛可靠性和收敛速度。但是其全局收敛性和收敛速度还需进一步的理论证明和其它实践检验，以保证此类算法的通用有效性。王素云等【】研究了两阶段启发式算法在带时间窗的车辆路径问题中的应用。论文对带时间窗约束的物流配送车辆路径问题，构造了一种两阶段启发式算法。第一阶段采用算法将客户聚类分群，第二阶段对每一客户子类采用禁忌搜索算法优化车辆路径。该方法降低了算法的复杂性。但是当客户点地理位置较分散时，如何将客户点的其他约束信息，如时间窗等应用到聚类中来，提前处理某些约束，还需进一步探讨。综上所述，可以得出以下几个方面问题需要进一步研究：（）在的路径选择方面：在配送过程中选择配送路线时，只是单纯的考虑路线的长度，对道路的拥挤程度对配送时间的影响考虑很少，而在实际配送过程中，道路拥挤直接影响配送成本和配送效率。（）在的求解方法方面：面对客户规模较大（），交通网络复杂的车辆线路优化问题，现有算法存在一些问题：精确算法求解大规模的显然是不现实的，因为该算法引入严格的数学方法，因而无法避开指数爆炸问题，从而使该类算法只能有效求解中小规模的，且精确算法的计算量一般随问题规模的增大呈指数增长，在实际中应用范围很有限；遗传算法、禁忌搜索算法、模拟退火算法、蚁群算法、粒子群算法等亚启发式及其混合算法则因问题规模增大时，劣解增多而大大降低了解的搜索效率，无法实现搜索时间和解的性能两者之间的平衡。研究意义车辆路径问题的求解方法一般分为精确算法和启发式算法。精确算法指可求出其最优解的算法，但对车辆路径问题来说，精确算法很难在合理的时间内得出最优解，其原因在于车辆路径问题是一类（）问题，这类问题一般具有大量的约束条件和变量，并且约束条件和变量的多少对计算时问是非线性的，即随着约束条件和变量的增多，会产生指数爆炸现象。同时，随着所考虑的约束条件的增多，除了要考虑成本的因素之外，还要考虑配送时间和环境等方面的因素，这就使问题的建模和求解变得更加复杂。而遗传算法、基于聚类分析和遗传算法的带时间窗车辆路径问题研究禁忌搜索算法、模拟退火算法、蚁群算法、粒子群算法等亚启发式及其混合算法则因问题规模增大时，劣解增多而大大降低了解的搜索效率，无法实现搜索时间和解的性能两者之间的平衡。因此，为解决大规模的车辆路径问题，需要有一种时间上耗费较少、求解性能较优的算法，来满足实际工作的需要。本文所指的大规模足指客户数比较大，以客户数为界限的。针对大规模车辆路径问题，本文提出应用聚类分析和遗传算法来求解大规模车辆路径问题，通过聚类分析把大规模的车辆路径问题简化为小规模的车辆路径问题，从而解决由于问题规模增大而引起解的搜索困难，然后对传统遗传算法进行改进，提高算法的整体求解效率，从而为解决大规模车辆路径问题提供一种新的思路和方法，为实际物流配送提供切实可行的线路优化手段，达到降低物流成本，提高企业利润和客户满意度的目的，本研究具有重要的现实意义。研究内容本文收集了国内外学者专家对车辆路径问题的相关研究成果，对文献资料进行整理、分类，作为数学模型建立的理论基础，提出应用两阶段法求解，即第一阶段，采用聚类分析对配送网点进行区域划分，将大规模简化小规模来求解；第二阶段是对同类中的客户点进行线路规划，本文采用全局搜索能力较强的遗传算法求解，并对遗传算法进行改进，然后用实现本文提出的算法，并以的标准数据中系列数据进行数值实验，得出用两阶段法具有更强的寻优性能。本论文的丰要研究内容如下：（）根据配送中心的条件、道路情况及客户的需求等实际情况，将车辆行驶的总路程尽量少、车辆延误时间尽量少作为目标函数的主要考虑因素，建立带时间窗车辆路径问题的数学模型。（）针对标准遗传算法存在的问题，提出用遗传算法求解问题时的改进策略，为下一步的研究做准备。（）应用聚类分析对配送网点进行配送区域划分，设计更适合于带时问窗车辆路径问题优化的改进型遗传算法，并通过实例进行验证。福建农林大学届硕士学位论文车辆路径问题的数学模型分析研究车辆路径问题（）是从旅行商问题（）演化而来，旅行商问题是车辆路径问题的一个特例，它只包括一条路径问题，且没有能力约束的。而有时间窗车辆路径问题是在经典车辆路径问题基础上根据学术研究和实际应用延伸和变化的一种型态，它们三者之间是一脉相承的、相互联系的。旅行商问题（）的数学模型旅行商问题可以描述为：安排一条旅行线路，使得旅行商从起点出发，经过每个城市一次，最终返回原地，而总的旅行距离最短，该问题的数学模型为【删：，刀）点集，表示旅行商要经过的城市，其中表示起点；（，歹），弧集，表示旅行商可能经过的路段集合；（，）彳）费用集合，劬表示旅行商经过对应路段（，）时的花费，如时间、距离、行驶费用等。求解即在加权图【，】中找到总费用最小的汉密尔顿（）回路。定义变量柳，三若弧窑贝乒线路上建立以下模型：口勖（一），”（），玎（）勋矿一（），勘（，），刀；，打（）目标函数（）使旅行商巡游费用最小；约束（），（）保证每个城市只被访问一次；约束（）为支路消去约束，即消去构成不完整线路的解。基于聚类分析和遗传算法的带时间窗车辆路径问题研究经典车辆路径问题（心）的数学模型经典车辆路径问题（）可具体描述如下：设有一场站（），共有辆货车，车辆容量为，有位顾客需要服务，每位顾客有其需求量，车辆从场站出发对客户进行配送服务最后返回场站，要求所有顾客都被服务，顾客需求由一次配送完成，不能违反车辆容量的限制，目的是所有车辆行驶的总距离最小。图一为示意图（图中矩形表示场站，小圆圈表示需要服务的顾客，箭头线表示车辆行驶路径）。图车辆路径问题示意图经典在满足以下约束条件情况下，求解辆车的总行驶成本最小：（）每条路径的起点和终点都是供货点；（）每个客户只应该被车辆服务一次；（）每条路径中的所有客户需求的总和不能超过车辆的载重量经典模型用数学语言可以描述为删：，：前舭噤辄就（圳，“，问否则刈，拈，厶球矿车辆枞囊需驰崎，朋，“）孙否则；【，刈，职拈，福建农林大学届硕士学位论文以最小化系统运行费用为目标，建立如下车辆路径问题模型：白肛（），村（七，）（）白（，刀）（）膏儿（）班扫（，）（）砸，（，刀）（），壮，；，）（一）打，）（，一，；七，）（）模型中，配送中心编号为，客户点编号为，配送中心和客户点均点（，拧）表示。目标函数（）是使车队总的服务费用最低；约束（）为车辆装载能力约束，即每条配送线路的送货量不能超过车的最大载重量；约束（）保证每个客户都被服务；约束（）保证车辆都从配送中心出发并返回到配送中心；约束（）、（）保证如果客户点，在车辆的行驶线路上，那么客户点，将由车辆服务。有时间窗车辆路径问题（心）的数学模型时间窗问题描述时间窗是一个时问段【，三丁，】，是由客户要求的最早服务时间兀和最晚服务时问，确定的一个服务时间区间。在的基础上给每个顾客加上服务所允许的时间窗（）约束，就扩展成了。时间窗车辆路径问题的分类由于时间窗车辆路径问题的复杂性，如果严格按照顾客设定的服务时问为其服务，可能造成企业的配送成本增加。如果允许在某些客户点适当地延误，可能使运输成本大为减少，即对该延误现象给予一定的惩罚。所以根据决策者在对客基于聚类分析和遗传算法的带时间窗车辆路径问题研究户满意和成本二者权衡时偏好的不同时，若按照客户满意度来分，时间窗还可以分为硬时间窗（，简称）和软时间窗（，简称）以及混合时间窗（，简称丁）三种情况。（）硬时间窗（，简称）：指配送车辆必须在规定时间段内将配送货物送达到顾客手中，顾客拒绝接受在此时问段之外提供的服务。如图为一惩罚函数（），当配送货物送达时间超过了规定的时间段【兀，三】，其惩罚值（）等于一个非常大的正值，以表示硬时间窗的限制。（，）乃上正图硬时司窗硬时间窗的车辆路径问题（）中，车辆可以在最早服务时间之前到达客户所在地，但必须等待直至到了最早服务时间才能对客户提供服务；另外车辆不能在最晚服务时间之后到达客户所在地。如在牛产系统中，送货车辆到达时问若迟于指定的最晚到达时问，会导致整个牛产线的延误和闲置，造成时间成本的增加和效率的降低，因此这种情况下往往不允许违背时间窗的约束。对于硬时间窗车辆路径问题来说，服务所有客户所需的车辆数目也是决策变量，一般来说，所用车辆越少，对应的成本也越小，如何用最少的车辆在不违背车辆容量及客户时间窗的约束的前提下，为所有客户提供服务，也是决策者关心的一个问题。因此在对硬时间窗车辆路径问题建模时确定的目标函数往往是多目标且多层次的，根据具体要求的不同，目标函数的层次也不尽相同。通常，首先最小化服务所有客户所需的车辆数目，因为每多增加一辆车意味着多增加一福建农林大学届硕士学位论文条服务路线和一名司机，其成本会高很多，而且需要的车辆越多，车队的购置成本也越高；其次，对于使用同样数目车辆的情况，最小化总的行驶路程或行驶时间。（）软时间窗（，简称）：指配送车辆如果无法将货物在特定的时段【兀，】内送到顾客手中，则必须按照违反时间的长短施以一定的罚金或其它惩罚法则。图就是一种可能的惩罚函数。（）乃上正图软时司窗带软时间窗的车辆路径问题相对带硬时间窗的车辆路径问题来说放松了对时问窗的约束，这是因为在实际情况中，由于道路交通流量，车辆的行驶速度以及客户的需求时间等不确定因素导致货物无法在规定的时间窗内送到，如果采用硬时问窗的约束进行优化，将导致成本非常高，甚至可能无解。而只要求车辆应尽可能在客户指定的时间窗内以最小的总成本为所有客户提供服务，允许一定程度的延误现象。显然，较具有更好的通用性。在实际运输规划中，决策者往往需要在客户满意度和成本二者之间权衡，偏好不同决定了可以允许延误的程度不同。在中，车辆如果在最早服务时间之前到达客户所在地，需等待直至到了最早服务时间后才能提供服务；如果在最晚服务时间之后到达客户所在地，则可能导致客户满意度降低，隐性成本的增加。因此应尽量避免延误现象的发生，如果发生，应加以惩罚，惩罚的具体程度可由决策者设定。在对建模时，表现为目标函数增加了一项惩罚项，它具体体现在目标函数值（对应服务成本）的增加。基于聚类分析和遗传算法的带时间窗车辆路径问题研究混合时间窗（，简称）：在系统中有些顾客属于硬时间窗，有些顾客属于软时间窗对同一顾客，又可能软、硬时间窗混合使用。在实际的配送工作中，车辆如果能在最佳时间段【丁，三兀】内将货物送达到顾客手中，则不处罚；若在图中的【口，兀】或，段内才送达，则顾客的满意度降低，将处以一定的惩罚转化为惩罚函数，并且顾客不接受在上述两个时间段以外的时间收货。（，）口乃乃，图混合时间窗此外，如果时间窗按形式来分有单边和双边时间窗之分，所谓单边时间窗足从双边时间窗中去掉了对最早服务时间的限制，客户不再要求车辆最早服务时间，而只要求在某个时间点之前为客户提供服务。目前研究最多的是带双边时问窗的车辆路径问题，即只有在客户指定的时问窗口内为其提供服务。若车辆在客户指定的最早时问之前到达客户所在地，则需要等待直到了客户要求的最早时间，才能对客户提供服务；此外，车辆必须在最晚服务时间之前为客户提供服务，否则不可行。有时间窗车辆路径问题的约束条件随着社会经济的不断发展，人们对物流配送的实效性要求越来越高，研究带时间窗车辆路径问题更加贴近实际，更具有实际意义，但带时间窗车辆路径问题本身的复杂性和难度，本文所研究的带时间窗车辆路径问题是指单车场、单车型、福建农林大学届硕士学位论文非满载、纯装货或纯卸货的带软时间窗车辆路径问题（擅）。在对建模时，确定的目标函数往往是多目标且多层次的，根据具体要求的不同，目标函数的层次也不尽相同，其需要实现的主要目标是准时到达与成本最低，也就是在满足客户对送货时间要求和其他需求的基础上，合理安排车辆路线，使得车辆总运行成本尽可能少。结合问题的实际背景，特作如下假设描述：（）车场在本问题中，仅存在单一的车场，且车场位置己经确定，车场拥有足够数量的车辆，保证满足所有客户的需求。（）车辆性质在本问题中，所有车辆必须从车场出发，经客户点装货（或卸货）后，必须回到车场，这样有利于车场对车辆进行管理调度所有的车辆均拥有相同的载重限制，不允许超载运行所有车辆的行驶速度均认为相同每辆车可以服务多个客户，但每个客户的货物只由一辆车配送。（）客户需求性质在本问题中，所有客户的位置均己知且固定，所有客户的需求也已知，且需求小于车辆的载重限制，客户对被服务时间有限制，所有客户的需求形式均相同，或全部为装货问题，或全部为卸货问题。（）道路性质在本问题中，考虑道路的实际交通情