《车辆路径问题》PPT课件

《《车辆路径问题》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第14章车辆路径问题（VehiclePathProblem）车辆路径问题，又称运输调度问题，简记VRP&VSP,包括两部分，其一是行车路线的设计，其二是出行时间表的安排。该问题1959年由Dantzig和Ramser提出的，是指在客户需求位置已知的情况下，确定车辆在各个客户间的行程路线，使得运输路线最短或运输成本最低，通过研究VRP可以合理使用调运工具，优化运输路线，降低企业物流成本。第14章车辆路径问题（VehiclePathProblem）14.1物流配送车辆优化调度的概述（IntroductionofVRPforLogisticsDistributi

2、on）14.1.1概述（Introduction）14.1.2路径特性（TheRouteCharacteristic）14.1.3常用的基本问题（TheBasicProblems）14.1.4车辆路径问题的求解方法（TheMethodofSolvingRouteProblem）14.2单中心非满载送货车辆路径问题启发式算法（HeuristicMethodsforOneCenterVRPwithNon-fullyLoaded）14.2.1禁忌搜寻法简介（Tabu-ResearchAlgorithm）14.2.2问题描述与符号表示（TheProblemandS

3、ymbol）14.2.3求解过程（Arithmetic）第14章车辆路径问题（VehiclePathProblem）14.3车辆调度的其他算法简介（SomeOtherAlgorithmsforVRP）14.3.1遗传算法（GeneticAlgorithm）14.3.2神经网络算法（NeuralNetworksAlgorithm）14.1物流配送车辆优化调度的概述14.1.1概述车辆路径问题一般定义为：对一系列装货点和(或)卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件(如：货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、

4、时间限制等)下，达到一定的目标(如：路程最短、费用最少、时间尽量少、使用车辆数尽量少等)。14.1物流配送车辆优化调度的概述14.1.1概述目前有关VRP的研究已经可以表示为：给定一个或多个中心（中心车库）一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，所载的货物不能超过它的容量。配送中心14.1物流配送车辆优化调度的概述14.1.2路径特性车辆路径问题的特性比较复杂，总的来说包含四个方面的属性：（1）地址特性包括：车场数目、需求类型、作业要求。（2）车辆特性包括：车辆数量、载重量约束、可运载品种约束、运行路线约束、工作时间约束。（3

5、）问题的其他特性。（4）目标函数可能是总成本极小化，或者极小化最大作业成本，或者最大化准时作业。14.1物流配送车辆优化调度的概述14.1.2路径特性车辆路径问题的特性导致了算法的多样性和复杂性。为简化问题的求解，常常应用一些技术将问题分解或转化成一个或几个已经研究过的基本问题，再用相应比较成熟的基本理论和方法，以得到原满意解。14.1物流配送车辆优化调度的概述14.1.3常用的基本问题（1）旅行商问题（2）带容量约束的车辆路线问题（3）带时间窗的车辆路线问题（4）收集和分发问题（5）多车型车辆路线问题（6）优先约束车辆路线问题（7）相容性约束车辆路线问题

6、（8）随机需求车辆路线问题14.1物流配送车辆优化调度的概述14.1.4车辆路径问题的求解方法由于车辆路径问题是个NP难题，为了找到满足约束条件的最优解，就必须检查很大的设计空间，而设计空间又是多维的非连续空间，很难找到一个规范的搜索集来系统地搜寻整个空间，所以很难得到全局的最优解或满意解。现代研究针对以上问题，现在已有很多方法。14.1物流配送车辆优化调度的概述14.1.4车辆路径问题的求解方法1.数学解析法此法以动态规划法、整数规划法、树状搜寻法等方式为主来进行求解，对于配送点数较少的情形能求得一个最优解，但若求解的节点数增加，则其结果相对变差，与实际

7、配送的情相差较大。14.1物流配送车辆优化调度的概述14.1.4车辆路径问题的求解方法2.人机互动法提供使用者借由人机互动的方式，结合使用者过去的经验，调整该模型的参数，以作为配送路线规划决策的依据。14.1物流配送车辆优化调度的概述14.1.4车辆路径问题的求解方法3.先分组再排路线法先将所有配送点分成数个群组，再分别对各个群组进行路线规划，如扫描法，根据所有配送点的分布，以极坐标的表示方法来呈现各配送点的位置，然后任意选取一配送点为起始点，依顺时针或逆时针的方向选取尚未指派的配送点，并以货车的容量或其他条件作为限制，进行车辆配送的分组作业，再以求解旅行

8、商问题的算法进行最优化的操作。14.1物流配送车辆优化调度的概述1