下载文档原格式
带软时间窗约束的车辆路径问题的混合算法研究及其应用车辆路径问题(Vehicle Routing Problems,VRP)是一个NP难问题,是物流领域中具有重要理论和实际意义的问题。
在现实生活中,有很多问题可以抽象为VRP问题,如银行押款车的行驶路线、快递分发包裹、工业垃圾回收、校车接送学生、餐馆送餐等。
选择合理的物流配送方案,可以降低企业物流开支,节约成本,提高效率,加速货物的流通过程,赚取更多的利润,对于一个企业的成败具有关键性意义。
在中国物流业快速发展的今天,对VRP问题的研究愈发重要。
带时间窗约束的 VRP 问题(Vehicle Routing Problems with Time Windows,VRPTW)是在基本VRP问题的基础上衍生而来,有着很高的研究价值。
本文致力于研究带重量约束和软时间窗约束的VRP问题(Capacitated Vehicle Routing Problems with Soft Time Windows,CVRPSTW)。
长期以来,国内外许多学者对这个问题进行了大量的研究和阐述,产生了许多优秀的算法。
在他们工作的基础上,利用VRP问题的数学模型,本文提出了一种分布式的多阶段混合启发式算法,目标是在合理的时间内取得较好的结果。
本文的主要工作包括:第一,实现单机版的多阶段混合启发式算法,包括使用模拟退火算法(Simulated Annealing,SA)对车辆数目进行优化,使用禁忌搜索算法(Tabu Search,TS)对违反时间窗代价和路线总行程距离进行优化。
在求解过程中,使用了多种不同的邻域生成方法,包括对部分元素的交换和重置的小邻域生成法、基于摧毁和重建思想的大邻域生成法,以减少在局部最优附近的重复搜索。
加入自适应存储(Adaptive Memory,AM)算法,当搜索陷入瓶颈时,从AM中产生新的邻域搜索中心,开始新一轮迭代搜索,使得搜索及时跳出瓶颈并向着好的方向前进,保证搜索的有效性和多样性。
带时间窗物流配送车辆路径问题摘要本题是一个带有时间窗的车辆路径安排问题（VRPTW问题）。
根据题目条件，本文建立了一个求解最小派送费用的VRPTW优化模型，采用遗传算法，给出了该模型的求解方法。
然后，对一个实际问题进行求解，给出了一个比较好的路线安排方式。
模型一（见5.1.2）针对问题一，在需求量、接货时间段、各种费用消耗已知的情况下，决定采用规划模型，引入0-1变量，建立各个约束条件，包括车辆的容量限制，到达每个客户的车辆和离开每个客户的车辆均为1的限制，总车辆数的限制，目标函数为费用的最小化，费用包括车辆的行驶费用，车辆早到或晚到造成的损失。
模型一的求解采用遗传算法（见5.1.3），对题目给出的实际问题进行求解，首先按照需求期望根据模型一得到一个比较好的方案，然后按照这一方案进行送货，在送货过程中，如果出现需求量过大的情况，允许车辆返回仓库进行补充。
模型一的思路清晰，考虑条件全面。
但最优解解决起来困难，遗传算法只是一种相对好的解决方法，可以找出最优解的近似解。
模型二的想法比较合理，易于实施，但还有待改进。
关键词：规划 时间窗 物流 车辆路径 遗传算法一、 问题重述一个中心仓库，拥有一定数量容量为Q 的车辆，负责对N 个客户进行货物派送工作，客户i 的货物需求量为i q ，且i q Q <，车辆必须在一定的时间范围[],i i a b 内到达，早于i a 到达将产生等待损失，迟于i b 到达将处以一定的惩罚，请解决如下问题：（1）给出使派送费用最小的车辆行驶路径问题的数学模型及其求解算法。
并具体求解以下算例：客户总数N=8,每辆车的容量Q=8（吨/辆）, 各项任务的货运量i q （单位：吨）、装货（或卸货）时间i s （单位：小时）以及要求每项任务开始执行的时间范围[],i i a b 由附录1给出，车场0与各任务点以及各任务点间的距离（单位：公里）由附件二给出，这里假设车辆的行驶时间与距离成正比，每辆车的平均行驶速度为50公里/小时，问如何安排车辆的行驶路线使总运行距离最短； （2）进一步请讨论当客户i 的货物需求量i q 为随机参数时的数学模型及处理方法。
带时间窗车辆路径问题的最优解带时间窗的车辆调度问题是物流配送系统的关键之关键，对它的研究越来越重视。
本文将建立物流管理中的带时间窗车辆路径问题的模型，并得到此模型的最优解，有一定的实用意义。
标签：带时间窗车辆路径问题物流管理组合优化一、提出问题在许多物流配送系统中，管理者需要采取有效的配送策略以提高服务水平、降低货运费用。
其中车辆路径问题是亟待解决的一个重要问题，此问题可描述如下：有一个货物需求点（或称顾客），已知每个需求点的需求量及地理位置，至多用K辆汽车从中心仓库（或配送中心）到达这批需求点，每辆汽车载重量一定，安排汽车路线使运输距离最短并且满足每条线路不超过汽车载重量和每个需求点的需求量且必须只能用一辆汽车来满足。
带时间窗车辆路径问题（VRPTW，vehicle routing problem with time windows）是在车辆路径问题中加入了客户要求访问的时间窗口，由于在现实生活中许多问题都可以归结为VRPTW来处理，但处理的好坏将直接影响到一个企业的效益和顾客的服务质量，所以对它的研究越来越受到人们的重视，目前对它的求解主要集中在启发式算法上。
20世纪90年代后，遗传算法、禁忌搜索算法、模拟退火算法、人工神经网络算法和动态蚁群算法等启发式算法的出现，为求解VRPTW提供了新的工具。
但是，遗传算法存在“早熟性收敛”问题，禁忌搜索算法、人工神经网络算法也存在一些不尽人意的地方，如何针对VRPTW的特点，构造简单、寻优性能优异的启发式算法，这不仅对于物流配送系统而且对于许多可转化为VRPTW求解的优化组合问题均具有十分重要的意义。
实际数据表明动态蚁群算法行之有效，不失为一种求解VRPTW的性能优越的启发式算法。
二、问题描述VRPTW可以描述如下：给定车辆集合V，需求点集合C和有向图G。
此有向图有|C|+2个顶点，顶点1,2,K,n表示需求点，顶点0表示离开时的中心仓库，顶点n+1表示返回时的中心仓库，把顶点0,1,2,3,K,n+1记作集合N。
带时间窗的车辆路径问题（VRPTW）是一种重要的组合优化问题，在许多实际的物流配送领域都有着广泛的应用。
该问题是对经典的车辆路径问题（VRP）进行了进一步扩展，考虑了车辆在每个节点进行配送时的时间窗约束。
VRPTW的数学建模和求解具有一定的复杂性，需要综合考虑车辆的路径规划和时间限制方面的因素。
本文将对带时间窗的车辆路径问题进行数学建模，并探讨一些常见的求解方法和算法。
一、问题描述带时间窗的车辆路径问题是一个典型的组合优化问题，通常可以描述为：给定一个具有时间窗约束的有向图G=(V,E)，其中V表示配送点（包括仓库和客户），E表示路径集合，以及每个节点v∈V都有一个配送需求q(v)，以及一个时间窗[Tmin(v),Tmax(v)]，表示了可以在节点v进行配送的时间范围；另外，给定有限数量的车辆，每辆车的容量有限，且其行驶速度相同。
问题的目标是设计一组最优的车辆路径，使得所有的配送需求都能够在其对应的时间窗内得到满足，且最小化车辆的行驶距离、行驶时间或总成本，从而降低配送成本和提高配送效率。
二、数学建模针对带时间窗的车辆路径问题，一般可以采用整数规划（IP）模型来进行数学建模。
以下是一个经典的整数规划模型：1. 定义决策变量：设xij为车辆在节点i和节点j之间的路径是否被选中，若被选中则为1，否则为0；di表示节点i的配送需求量；t表示车辆到达每个节点的时间；C表示车辆的行驶成本。
2. 目标函数：目标是最小化车辆的行驶成本，可以表示为：minimize C = ∑(i,j)∈E cij*xij其中cij表示路径(i,j)的单位成本。
3. 约束条件：（1）容量约束：车辆在途中的配送总量不能超过其容量限制。
∑j∈V di*xij ≤ Q, for i∈V（2）时间窗约束：Tmin(v) ≤ t ≤ Tmax(v), for v∈Vtij = t + di + dij, for (i,j)∈E, i≠0, j≠0（3）路径连通约束：∑i∈V,x0i=1; ∑j∈V,xji=1, for j∈V（4）路径闭合约束：∑i∈V xi0 = ∑i∈V xi0 = k其中k表示车辆数量。
物流系统中的配送路径优化与时间窗问题章节一：引言在物流行业中，配送路径优化与时间窗问题一直是一个重要的研究方向。
随着物流网络的不断扩大和配送需求的增加，如何优化配送路径，提高物流效率成为了物流企业亟待解决的问题。
本文将从配送路径优化和时间窗问题两个方面展开论述，分析其意义、方法和应用。
章节二：物流系统中的配送路径优化2.1 配送路径优化的意义配送路径优化是指在给定的物流网络中，通过合理的路径规划和调度，使得物流资源得到最优利用、节约成本和提高效率。
优化配送路径可以降低货物运输时间，减少运输成本，提高客户满意度。
在物流系统中，配送路径优化是实现高效物流运作的关键环节。
2.2 配送路径优化的方法配送路径优化可以应用多种算法和模型进行求解。
常见的方法包括启发式算法、模拟退火算法、遗传算法等。
这些算法可以通过对问题进行建模和求解，得出最优或近似最优的配送路径方案。
2.3 配送路径优化的应用配送路径优化在物流企业中有广泛的应用。
例如，电商平台需要确定最佳的配送路径，快递公司需要调度物流车辆进行最优路径规划。
在城市物流配送中，通过优化路径可以实现更快速、高效的派送，减少交通拥堵，提高快递员的配送效率。
章节三：物流系统中的时间窗问题3.1 时间窗问题的意义时间窗问题是指在配送过程中，为了满足客户需求和物流运作的要求，对配送时间设置了一定的限制和约束。
合理管理时间窗可以有效提高配送效率和服务质量。
3.2 时间窗问题的解决方法针对时间窗问题，可以通过线性规划、模糊数学、动态规划等方法进行求解。
线性规划可以将配送路径纳入到约束范围内，以最小化总配送时间为目标进行优化。
模糊数学可以处理时间窗的不确定性和模糊性，更加灵活地规划配送路径。
3.3 时间窗问题的应用时间窗问题广泛应用于物流配送、交通管理等领域。
在电商配送中，通过时间窗的合理安排，可以确保客户在特定时间段内收到货物，提升客户满意度。
在城市交通管理中，合理设置交通信号灯的时间窗可以减少交通拥堵，提高交通流畅度。
带时间窗约束的车辆路径问题模型构建及求解下载提示：该文档是本店铺精心编制而成的，希望大家下载后，能够帮助大家解决实际问题。
文档下载后可定制修改，请根据实际需要进行调整和使用，谢谢！本店铺为大家提供各种类型的实用资料，如教育随笔、日记赏析、句子摘抄、古诗大全、经典美文、话题作文、工作总结、词语解析、文案摘录、其他资料等等，想了解不同资料格式和写法，敬请关注！Download tips: This document is carefully compiled by this editor. I hope that after you download it, it can help you solve practical problems. The document can be customized and modified after downloading, please adjust and use it according to actual needs, thank you! In addition, this shop provides you with various types of practical materials, such as educational essays, diary appreciation, sentence excerpts, ancient poems, classic articles, topic composition, work summary, word parsing, copy excerpts, other materials and so on, want to know different data formats and writing methods, please pay attention!带时间窗约束的车辆路径问题模型构建及求解引言在物流和运输领域，车辆路径问题（Vehicle Routing Problem，VRP）是一个经典的优化问题，旨在有效安排车辆的路线，以满足一组客户的需求，同时最小化总成本或最大化总利润。
时间依赖型多配送中心带时间窗的开放式车辆路径问题研究一、本文概述本文致力于探讨一种复杂而实际的物流优化问题——时间依赖型多配送中心带时间窗的开放式车辆路径问题（TimeDependent MultiDistribution Center Vehicle Routing Problem with Time Windows, 简称TDMDCVRPTW）。
在现实世界中，物流企业在运营过程中时常面临此类挑战：需要从多个配送中心出发，向分布在不同地理位置且具有特定服务时间窗口的客户配送货物，并且行驶时间受到交通状况实时变化的影响，即存在显著的时间依赖性。
本研究旨在构建一个全面且实用的模型来解决这一难题，通过整合时间依赖性路况对行驶时间和路线选择的影响，同时考虑各个配送中心之间的协同运作和资源共享，以及客户节点的时间窗约束。
我们提出了一种改进的算法策略，旨在有效降低总行驶距离、减少行车时间以及提高服务水平，确保在满足所有客户需求的前提下，达到物流系统的高效运行与资源最优配置。
本文结构上，首先深入剖析问题背景与相关理论基础，接着详述所构建的数学模型及其关键参数定义然后介绍并阐述用于求解该类问题的设计思路与优化算法最后通过实例分析和仿真验证，对比现有方法评估本文算法的有效性和实用性，从而为相关领域的实践操作提供理论指导和技术支持。
二、相关理论与模型构建时间依赖型车辆路径问题（TimeDependent Vehicle Routing Problem, TDVRP）是经典车辆路径问题（Vehicle Routing Problem, VRP）的扩展。
在TDVRP中，车辆行驶时间不仅取决于路程长度，还受交通拥堵、时段、天气等因素的影响。
TDVRP更贴近现实情况，其核心在于如何在时间依赖的路网中优化车辆路径，以最小化总成本。
多配送中心车辆路径问题（MultiDelivery Center Vehicle Routing Problem, MDCVRP）是VRP的另一个变体。
物流配送路径规划中的时间窗问题研究随着电子商务的蓬勃发展，物流配送成为了供应链管理中不可或缺的环节。
为了提高送货效率、减少成本和满足顾客需求，物流公司面临着一个重要的问题，即如何合理规划物流配送路径。
而其中一个关键因素就是时间窗问题，也就是要在规定的时间窗口内完成配送任务。
一、时间窗问题的定义和意义时间窗问题是指在物流配送中，每个配送点都有一个规定的时间段，配送员必须在这个时间窗口内赶到该点并完成送货任务。
这些时间窗口可以是固定的，也可以是根据客户需求而变化的。
时间窗问题的解决对于物流公司具有重要意义。
首先，合理安排时间窗可以提高配送效率，从而减少配送成本，提高服务质量。
其次，根据不同的时间窗，物流公司可以优化配送路线，减少车辆行驶时间和里程，减少能源消耗，降低环境污染。
二、时间窗问题的挑战与解决方法时间窗问题的主要挑战在于如何在有限的时间窗内，找到最优的配送路径。
为了解决这一问题，学术界和业界提出了许多方法和算法。
1.贪心算法贪心算法是一种常用于解决最优化问题的方法，在时间窗问题中也有应用。
它通过每次选择最具吸引力的任务或路径，逐步构建最终解。
然而，由于贪心算法的局部最优性，可能无法得到全局最优解。
2.启发式算法启发式算法是一种通过规则和经验寻找解的方法，常用的有遗传算法、模拟退火算法等。
这些算法通过模拟自然界的进化过程或物质的状态转变过程，寻找最佳解。
启发式算法在时间窗问题中的应用可以得到较好的结果，但计算复杂度较高。
3.精确算法精确算法是指通过数学建模和优化求解的方法，保证找到全局最优解。
其中最常用的是线性规划和整数规划。
然而，精确算法的计算复杂度较高，适用于小规模问题。
三、时间窗问题的应用案例时间窗问题在实际物流配送中有广泛的应用，并取得了显著的效果。
以市中心快递配送为例，拥有数十个配送点，每个点有固定的时间窗口。
为了优化配送路径，可以使用遗传算法进行求解。
首先，根据配送点之间的距离和时间窗的限制，构建一个遗传算法模型。
带时间窗物流配送车辆路径问题摘要本题是一个带有时间窗的车辆路径安排问题（VRPTW 问题）。
根据题目条件，本文建立了一个求解最小派送费用的VRPTW 优化模型，采用遗传算法，给出了该模型的求解方法。
然后，对一个实际问题进行求解，给出了一个比较好的路线安排方式。
模型一（见，在需求量、接货时间段、各种费用消耗已知的情况下，决定采用规划模型，引入0-1变量，建立各个约束条件，包括车辆的容量限制，到达每个客户的车辆和离开每个客户的车辆均为1的限制，总车辆数的限制，目标函数为费用的最小化，费用包括车辆的行驶费用，车辆早到或晚到造成的损失。
模型一的求解采用遗传算法（见，对题目给出的实际问题进行求解，得到3首先按照需求期望根据模型一得到一个比较好的方案，然后按照这一方案进行送货，在送货过程中，如果出现需求量过大的情况，允许车辆返回仓库进行补充。
模型一的思路清晰，考虑条件全面。
但最优解解决起来困难，遗传算法只是一种相对好的解决方法，可以找出最优解的近似解。
模型二的想法比较合理，易于实施，但还有待改进。
关键词：规划 时间窗 物流 车辆路径 遗传算法一、 问题重述一个中心仓库，拥有一定数量容量为Q 的车辆，负责对N 个客户进行货物派送工作，客户i 的货物需求量为i q ，且i q Q <，车辆必须在一定的时间范围[],i i a b 内到达，早于i a 到达将产生等待损失，迟于i b 到达将处以一定的惩罚，请解决如下问题：（1）给出使派送费用最小的车辆行驶路径问题的数学模型及其求解算法。
并具体求解以下算例：q（单位：客户总数N=8,每辆车的容量Q=8（吨/辆）, 各项任务的货运量is（单位：小时）以及要求每项任务开始执行的时间吨）、装货（或卸货）时间ia b由附录1给出，车场0与各任务点以及各任务点间的距离（单位：公,范围[]i i里）由附件二给出，这里假设车辆的行驶时间与距离成正比，每辆车的平均行驶速度为50公里/小时，问如何安排车辆的行驶路线使总运行距离最短；q为随机参数时的数学模型及处理方（2）进一步请讨论当客户i的货物需求量i法。
二、问题分析本题主要在两种不同情况下，研究使派送费用最小的车辆行驶路径问题。
车辆行驶派送的费用主要包括运输成本、车辆在客户要求到达时间之前到达产生的等待损失和车辆在客户要求到达时间之后到达所受惩罚等等。
为满足派送费用最小的需求，即要使所选行车路径产生的总费用最小，从而确定出最佳的车辆派送方案。
q固定时，首先，我们根据题意，取若干辆车进行送当客户i的货物需求量i货，然后，主要考虑每辆车各负责哪些客户的送货任务，我们可以给出满足题中限制条件的很多参考方案供选用，并考虑以所选行车路径产生的总费用最小为目标的情况下，建立最优化模型确定最佳的车辆派送方案。
q为随机参数时，我们首先可以简化随进一步讨论，当客户i的货物需求量i机模型，根据客户i的货物需求量的期望与方差，确定每天应该运送给客户i的q，再根据第一题，确定最佳的车辆派送方案。
货物量，即i但考虑到客户的储存能力有限及货物在客户处的储存费用，客户不需要将一天的货物一次性接收完，只要满足缺货的情况出现的概率很低，客户可以让配送中心一天几次送货，这样可以得到很多满足约束的方案，考虑以单位时间的储存费用最小为目标，建立最优化模型，确定配送中心给每位客户每次的配送量、配送周期与最有车辆行驶路径。
三、模型假设（1）每个客户的需求只能由一辆配送车满足；（2）每辆车送货时行驶的路程不超过它所能行驶的最远路程；（3）中心仓库的车辆总数大于或等于当派送费用最小时所需的车辆数；（4）从配送中心到各个用户、各个用户之间的运输距离已知；（5）配送中心有足够的资源以供配送。
四、符号说明五、模型的建立和求解5.1 问题一模型的建立及求解：中心仓库为了给N个客户派送货物，供发出m辆车，为了派货的节约和方便，每辆车载着适量的货物出发，可以给某一片的若干个满足约束条件的客户派送货物，见图一：图一中心仓库派送货物图中心仓如上图库派送货物时，必须满足约束条件：（1）各个客户群的总需求小于或等于运输车的装载量；（2）每个客户都必须且只能由一辆运输车运输所需货物；（3）运输车为每位客户开始服务的时间必须尽可能在时间窗内。
根据如上的约束条件，我们可以得到很多可行解，但考虑到以所选行车路径产生的总费用最小为目标的情况下，我们可以建立最优化模型确定最佳的车辆派送方案，最优路径产生图如下：图二最优路径产生图（1）中心仓库使用车辆数量的确定设配送中心需要向N个客户送货，每个客户的货物需求量是gi（i＝1，2，…..N），每辆配送车的载重量是Q，且gi<Q。
首先为了安排路线需要对要使用的车辆数有一个估计。
在现实情况中，货物装（卸）车越复杂，约束条件越多，一辆车的实际载货量就越小。
在本文中使用文献[1]的公式来确定需要的车辆数m：[ ]表示取整，a为参数，0<a<1。
约束条件越多，货物装（卸）越复杂，a 值越小。
参考文献[2]，取a为0.85。
（2）引入0—1变量：x表示车辆s是否从客户i行驶到客户j。
定义其为0—1变量，则1)ijsy表示客户i的任务由车辆s完成。
同样定义其为0—1变量，则2)is（3）非线性规划模型的建立：a．目标函数的确定。
题目要求所选行车路径产生的总费用最小，我们确定总费用为目标函数，记为Z。
总费用由运输成本A、等待损失B和迟到所收惩罚C组成，根据题意有：所以，总费用Z最小化为：b．约束条件的确定。
约束1：车辆k 的运送总重量应不超过车辆的最大载重，即车辆有一定的运送能力，则可引入约束条件，1Ni isi q yQ =≤∑ (},,2,1{m k ∈∀)约束2：每个客户只能由一辆车来配送，则可引入约束条件， 约束3：保证到达一个客户的车辆也离开该客户，则可引入约束条件，111m Nijss i x===∑∑ (1,2,3,,;j N =)111mNijks j x===∑∑ (1,2,3,,;i N =)c ．变量之间关系的确定由上可确定等待时间i D ，超时时间i X 为： 车辆k 从客户i 到客户j 需经过两段时间ij t 为：设车辆为客户i 运送完货物后即为客户j 运送，则到达客户i 处时间i t 和到达客户j 处时间j t 之间的关系为：d ．此非线性规划模型为：我们采用遗传算法解决上面的问题： 1．编码采用自然数编码，即序数编码。
货物运输路线可以编成长度为N+m 的染色体11121s 21210,,,,0,,,0,,0,,,)t m mw i i i i i i i (，，其中，ik i 表示第ik i 项任务。
0表示车场，m 表示完成任务所需的车辆数。
2.出生初始群体初始群体随机产生，即产生N 项货物运输任务点的全排列，如12,,,N i i i ，如果11s ijj qQ -=≤∑，且1sij j q Q =>∑，将s 至N 的数向后移动一位，将0插入第s 位。
接着，继续上述操作，直到m 个0全部插入为止。
这样就构成了一条初始染色体。
用这种方法构造一个群体的染色体。
如：82576314，该编码插零之后变成0825*******。
它代表着需要三辆车运输货物。
其中，第1辆车行走路线为08250，即从仓库出发到依次到8、2、5商店再回到仓库。
第2辆车行走路线为07630，第3辆车行走路线为0140。
3.适应度函数适应度函数取'k kbz f z =，其中k f 为染色体k v 的适应度，b 为常数，'z 为初始种群中最好的染色体的运输成本，k z 为染色体k v 对应的运输成本。
4.遗传算子选取最佳保留的轮盘赌复制法进行染色体的复制。
变异算子采用反转变异。
交叉算子用最大保留交叉，其操作过程为：a) 若染色体交叉点处的两个基因都为0，则直接进行顺序交叉运算； b) 若染色体交叉点处的基因不全为0，则将交叉点左移（右移），直到左右两个交叉处的基因都为0，再进行顺序交叉运算。
5.算法的实现步骤Step1：采用自然数编码的方式，构造表示可行车路线的染色体；Step2：设置控制参数，包括交叉率0.7c p =、变异率0.1m p =、群体规模10n =； Step3：初始化，令0d =，随机产生初始群体(0)p ，群体中包括n 个染色体，每个染色体代表一条行车线路； Step4：令1i =；Step5：将群体()p d 中的第i 个染色体译为线路长度； Step6：计算适应度；Step7：若满足算法终止条件，则停止，否则继续； Step8：1ii =+；Step9：若i n ≤，回到step5，否则，转step10；Step11：进行最大保留交叉、基于位的变异和倒位操作； Step12: 1dd =+；Step13：若满足算法终止条件，则停止，否则转step4。
运用matlab 软件编写程序得到在车辆总行程最短的条件小的派送方案为：从上面解出的派送方案可以看出，上面的每条路线在车辆送完货物后，直接从最后一个客户处返回中心仓库，我们通过求中心仓库到各个客户的最短路径可以发现，上面的返回路线不是最优的，返回路线可以经过某些客户使得所走路线最短。
公里。
5.2 问题二模型的建立及求解：在问题一中，根据已知的各个商店的需求分布，根据遗传算法求解，预先确定一条总费用最小的路径（或者虽不是最优路径，但是此结果能够接受的）。
车辆沿该路径服务商店，因此服务商店的顺序固定不变。
而问题二中，在车辆服务商店的过程中，事先并不知道商店的需求量。
而这个不确定信息要随着车辆的服务逐步确定，商店具体的需求只有车辆到达用户后才确定。
这样第一问的求解方法得到的路径并不适用于第二问的求解。
假设：（1）商店的需求变化符合正态分布，第i 个商店的需求量的期望和方差分别为i μ和2i σ。
（2）商店的供货可以分为多次补充但在每次供货中最大程度满足用户需求，即只有出现当前车载余量小于用户需求量时才出现下一次的供货。
基于第一问解决了在已知用户需求概率情况下，确定一个服务方案，满足所有n 个商店的需求并且使车辆期望行程费用最小这个问题。
我们由假设可知，第i 个商店的需求量的期望为i μ，则由需求量的期望得到一个使车辆期望行程费用最小的服务方案，称该方案为A 。
当用户的需求未知（当车辆服务商店时需求变成已知量）时，由于用户的需求量在区间(3)i i μσ±的概率是96%，而在区间外的事件可以看成小概率事件，由小概率事件定理可知，在一次试验中，小概率事件可以看成不可能事件。
由此可知，用户需求量就在区间(3)i i μσ±里。
用户需求在区间(3)i i μσ±里，而需求决定服务方案。
