模拟退火算法节约里程法求解VRP问题Matlab程序

目 录 第五章模拟退火算法求解VRP问题...........................................................................................1 5.1车辆路径问题（VehicleRoutingProblem,VRP）..........................................................1 5.2节约里程法（C-W）及其求解思路................................................................................1 5.3节约里程法Matlab程序实现..........................................................................................6 5.4节约历程法算例求解.....................................................................................................14 （1）算例E-n22-k4，最优解375.......................................................................................14 （2）算例E-n23-k3，最优解569.......................................................................................15 （3）算例E-n101-k14，最优解1077.................................................................................16 5.5模拟退火法求解VRP问题的Matlab程序..................................................................19 1第五章 模拟退火算法求解VRP问题 讲解标准的车辆路径问题以及节约里程法、模拟退火算法求解VRP问题的Matlab程序。[e-mail],201807275.1车辆路径问题（VehicleRoutingProblem,VRP）车辆路线问题（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。由此不难看出，旅行商问题（TravelingSalemanProblem,TSP）是VRP的特例，由于TSP问题是NP难题，因此，VRP也属于NP难题。基本的VRP问题可以描述为：设有一场站（depot），共有M辆货车，车辆容量为Q，有N位顾客（customer），每位顾客有其需求量D。车辆从场站出发对客户进行配送服务最后返回场站，要求所有顾客都被配送，每位顾客一次配送完成，且不能违反车辆容量的限制，目的是所有车辆路线的总距离最小。车辆路线的实际问题包括配送中心配送、公共汽车路线制定、信件和报纸投递、航空和铁路时间表安排、工业废品收集等。5.2节约里程法（C-W）及其求解思路5.2.1 算法说明算例 假设公司具有特定容量的车辆若干，需要从配送中心向6个客户点配送顾客需求数量的产品，优化目标是安排几辆车以及每辆车的行车路径，使得在满足全部顾客需求的基础上运输里程最短。其中：（1）6个需求节点需求量依次为：28、35、30、40、45、25，车辆容量为100。（2（35.2的启法，易的运送（bi和继续2）车辆容）产品数本算例客户2.2 C‐W节C-W节约启发式算法虽然C-W的获取相对C-W算法图5.2（a）送至i后再返b）中安排一j所需的物续行驶至j处量都是相同量也是产品户相互间距1243图节约算法简约算法是有法(G.ClarkeaW节约算法对比较好的可进行成本节）中安排了返回0，另一辆车将i和物品全部装上处将j所需同的，车辆品的容量；距离和布局如430655072275265图5.1VRP算简介 Clarke和WandW.Wrig一般情况下可行解，而节约的逻辑图5.2C-W了两辆车进行另一辆车从和j所需的上车，然后需的物品卸载2辆数量足够多如图5.1所0453673353745892043算例节点距Wright在ght1964)，下不能获取而且求解思路辑可以从图2W节约算法行货物的运0将j所需的物品一次性后先行驶至载下来，最多；所示。36503344060距离和布局1964年提出作为相对较取CVRP的最路简单明了2中两种运的基本逻辑运输，即一辆需的物品运送性运送至ii处将i所需最后返回0。54915图出的一种求较早提出的最优解，但。运输方案的对辑辆车从0将送至j后再返和j，即该需的物品卸另ijc为从节求解经典CV的一种启发式但是却可以很对比来体现将i所需的物返回0；图该辆车先从卸载下来，然节点i至节VRP式算很容现。物品图5.20将然后节点j的运本，必然车辆C-W大化法，可以的具（1（2运输成本（ijS为（b基于三角不然大于零。辆容量将多W算法另一化节约。C-W算法顺序合并过以允许多条不论哪种合具体数值来）给出任2）计算任或运输里程）图方案要不等式原理当物品配送个节点的运一个需要解中里程节约过程中每次条路径的合并合并程序，来说明。任意节点对之0123456注：表中节任意两个需求程），aD为要比（a）图理，只要将两送的客户数量运输集中到解决的任务就约的合并过次运算中只进并。该算法的前之间的距离表5.10130节点0为配求节点对合表5.2两11523453为（a）图的图方案节约两个节点分量较多，地到一辆车运输就是进行运过程分为两种进行一条路前期步骤都离，给出所有节点间相互236567437252配送中心，其合并共同运输两点合并的里234522533809110的运输成本，运输成本分别运输组合地理分布没有输，从而最运输任务合并种：序贯节约路径的合并都是一样的有需求节点的互距离45535450742789204960其他节点为输所能节约里程节约456310513028007255473867，bD为（b（里程），则合成一次运有特定规律最大程度的节并从而实现约里程法和，而同步合，下面以图的需求量和6285365404315为需求点。约的里程；b）图的运输则有下式成运输，节约量律时，如何根节约运输里现运输里程的和并行节约里合并每次运算图5.1所示算和车辆容量数输成成立：量ijS根据里程，的最里程算中算例数据；46以表5.2中第一行第二列的数据52为例做简要说明，该数据（结合图5.2）表示如果将派两辆车分别给需求点1和需求点2送货改为使用一辆车给需求点1和需求点2送货车辆运行距离的节约辆，即：如果两辆车分别送货，车辆运行距离为：01100220cccc=30+30+65+65=190；如果一辆车集中送货，车辆运行距离为：011220ccc=30+43+65=138；节约里程为：190-138=65。（3）将需求节点节约里程按照降序排列行号节点对节约量13-4：10022-4：9132-3：8043-5：6355-6：6763-6：5571-2：5284-5：4794-6：38101-4：33112-5：30122-6：28131-3：25141-5：10151-6：5节点对的数量应该有11Nii个。5.2.3 C‐W节约算法程序实现基本流程 （1）序贯节约里程法序贯节约里程法是指按顺序逐步生成全部路径，即每次搜索只生成一条路径。以上面的算例为例，说明序贯节约里程法的一般步骤：Step1：安排第一辆车的路径。首先考虑节点3和4能不能合并到一条路径，生成0-3-4-0的路径，由节点3和节点4的需求量分别为30和40，可知需求总量70，可以由一辆车运输，因而先生成路径0-3-4-0；然后再看节约里程表中第二行为2-4，由于节点4在已经生成的路径中，因此考虑节点2和节点4能不能5合并，即路径0-3-4-2-0是否可行，节点2的需求量为35，同节点3和4的需求量汇总起来共105，大于车辆的容量，因而路径0-3-4-2-0不可行；再看节约里程表中第三行为2-3，同样容量超限，所以这一行忽略；再看节约里程表第4行3-5，同样容量超限，所以这一行忽略；再看节约里程表第5行5-6，这两个节点都没有出现在当前的路径中，而序贯节约里程法一次只生成一条路径，因此这一行暂时也忽略；再看节约里程表第6行为3-6，考虑节点6和3能不能合并，即路径0-3-4-2-0是否可行，因为节点6的需求量为25，可以加入路径，从而生成路径0-6-3-4-0；依次类推，可以看出最后生成第一辆车的路径为0-6-3-4-0。根据该路径将节约里程表中所有同3、4、6的行删除后，获得新的节约里程表如下：行号节点对节约量11-2：5222-5：3031-5：10Step2：安排第二辆车的路径。首先考虑节点1和2能不能合并到一条路径，生成0-1-2-0的路径，由节点1和节点2的需求量分别为28和35可知需求总量63，可以由一辆车运输，因而生成路径0-1-2-0；然后再看节约里程表中第二行为2-5，考虑节点2和节点5能不能合并，即考察路径0-1-2-5-0是否可行，节点5的需求量为45，同节点5和6的需求量汇总起来共108，超出车辆容量，因而路径0-1-2-5-0不可行；再看节约里程表中第三行1-5，考虑节点1和节点5能不能合并，同样容量超限；因此第二辆车的路径为：0-1-2-0。将节约里程表中涉及节点1和节点2的行全删除，节约里程表结束。Step3：查看已安排路径，发现节点5还没有安排车辆，最后第三辆车的路径为：0-5-0。全部节点安排车辆结束。通过序贯节约里程法可得三条路径：0-6-3-4-0，0-1-2-0，0-5-0，三条路径的运行距离分别为：141、138、108，总运行距离为385。（2）并行节约里程法并行节约里程法是指在一次搜索中并行生成全部路径。以上面的算例为例，说明并行节约里程法一次搜索步骤中的处理逻辑：Step1：查看节约里程表第一行为3-4，考虑节点3和4能不能合并到一条路径，生成0-3-4-0的路径，由节点3和节点4的需求量分别为30和40，可知需求总量70，可以由一辆车运输，因而生成路径0-3-4-0（路径A）；Step2：再看节约里程表中第二行为2-4，由于节点4在已经生成的路径中，因此考虑节点2和节点4能不能合并，即路径0-3-4-2-0是否可行，节点2的需求量为35，同节点3和4的需求量汇总起来共105，大于车辆的容量，因而路径0-3-4-2-0不可行；再看节约里程表中第三行为2-3，同样容量超限，所以这一行6忽略；再看节约里程表第4行3-5，同样容量超限，所以这一行忽略；Step3：再看节约里程表第5行5-6，这两个节点都没有出现在当前的路径中，并行节约里程法一次需要生成全部路径，因此考虑节点5-6能不能合并到一条路径，生成0-5-6-0，由于节点5和节点6的需求量分别为：45、25，可知需求总量70，可以由一辆车运输，因此生成路径0-5-6-0（路径B）；Step4：再看节约里程表第6行为3-6，这两个节点分别在路径A和路径B中，因此判断两条路径能不能生成路径：0-5-6-3-4-0。由于路径A需求总量为70，路径B需求总量也为70，两条路径总量140超出车辆的容量，所以这一行忽略；Step5：再看节约里程表第7行为1-2，这两个节点都没有出现在当前的路径中，并行节约里程法一次需要生成全部路径，因此考