车辆路径问题
更新时间:2023-11-29 13:43:01 阅读量: 教育文库 文档下载
一、车辆路径问题描述和建模 1. 车辆路径问题
车辆路径问题(Vehicle Routing Problem, VRP),主要研究满足约束条件的最优车辆使用方案以及最优化车辆路径方案。
定义:设G={V,E}是一个完备的无向图,其中V={0,1,2…n}为节点集,其中0表示车场。V,={1,2,…n}表示顾客点集。A={(i,j),I,j∈V,i≠j}为边集。一对具有相同装载能力Q的车辆从车场点对顾客点进行配送服务。每个顾客点有一个固定的需求qi和固定的服务时间δi。每条边(i,j)赋有一个权重,表示旅行距离或者旅行费用cij。
标准车辆路径问题的优化目标为:确定一个具有最小车辆数和对应的最小旅行距离或者费用的路线集,其满足下列约束条件:
⑴每一条车辆路线开始于车场点,并且于车场点约束; ⑵每个顾客点仅能被一辆车服务一次
⑶每一条车辆路线总的顾客点的需求不超过车辆的装载能力Q
⑷每一条车辆路线满足一定的边约束,比如持续时间约束和时间窗约束等。 2.标准车辆路径的数学模型:
对于车辆路径问题定义如下的符号:
cij:表示顾客点或者顾客点和车场之间的旅行费用等 dij:车辆路径问题中,两个节点间的空间距离。
Q:车辆的最大装载能力 di:顾客点i的需求。
δi:顾客点i的车辆服务时间
m:服务车辆数,标准车辆路径问题中假设所有的车辆都是同型的。 R:车辆集,R={1,2….,m}
Ri:车辆路线,Ri={0,i1,…im,0},i1,…im?V,,i?R。 一般车辆路径问题具有层次目标函数,最小化车辆数和最小化车辆旅行费用,在文献中一般以车辆数作为首要优化目标函数,在此基础上使得对应的车辆旅行费用最小,下面给出标准车辆路径问题的数学模型。
下面给出标准车辆路径问题的数学模型。 对于每一条弧(I,j),定义如下变量:
xijv=
1 若车辆v从顾客i行驶到顾客点j0 否则
yiv=
1 顾客点i的需求由车辆v来完成
0 否则
mnnm
minF x =M ni=1 i=1x0iv+ i=0 j=0 v=1xijv.cij (2.1)
车辆路径问题的数学模型可以表述为:
n, mv=1 i=0xijv≥1 ?j∈V (2.2)
n
ni=0xipv? j=0xpjv=0 ?p∈V,v∈R (2.3) , mv=1yiv=1 ?i∈V (2.4) ni=1diyiv≤Q ?v∈R (2.5) ,yiv= ni=1xijv ?j∈V,v∈R (2.6)
式中,F x 表示目标函数,M为一个无穷大的整数,通过在目标函数中引入
参数M,能够保证算法在求解车辆路径问题时以车辆数为第一优化目标,以车辆旅行费用作为第二优化目标,也就是一个具有较少车辆数的解比一个具有较大车辆数但是较小车辆旅行距离的解好。约束条件(2.2)表示每个顾客点至少被车辆服务一次;约束(2.3)为车流约束,它要求一辆车到达一个顶点(车场或者顾客点)完成服务后必须离开这个顶点;约束条件(2.4)表示顾客点i只能由一辆车来服务。约束条件(2.5)为车辆能力约束,它表示车辆v服务的路线上的顾客点的需求量之和不能大于车辆的装载能力Q;约束条件(2.6)表示顾客点j只能由来自服务点i的所有车辆中的一辆车来服务。
车辆路径问题属于NP-hard问题,当顾客点数量大于50个时,用精确算法不能求出算法的最优解。相反利用问题特定信息或自然隐喻在中等计算时间内的获得车辆路径问题的次优解或满意解得启发式算法则成为研究的重点。下面介绍一种常用的启发式算法:遗传算法
3.遗传算法基本原理和步骤
遗传算法(Genetic Algorithm, GA),是一类以达尔文自然进化论与遗传变异理论为基础的求解复杂全局优化问题的仿生型算法,它借鉴生物界自然选择和自然遗传机制,以概率论为基础,在解的空间中进行随机化搜索,最终找到问题的最优解。
遗传算法的基本步骤为:从一个具有M个体的初始种群出发,不断循环的执行选择、交叉、变异操作,直到满足停止准则。标准遗传算法的主要步骤可描述如下:
⑴ 初始化,随机产生初始种群,个体数目一定,每个个体表示为染色体的基因编码;
⑵ 计算个体适应度,并判断是否符合优化准则,若符合,输出最佳个体及其代表的最优解,并计算结果,否则转向第3步;
⑶ 依据个体适应度选择再生个体,适应度高地个体被选中的概率高,适应度底的个体可能被淘汰;
⑷ 按照一定的交叉概率和交叉方法,生成新个体; ⑸ 按照一定的变异概率和变异方法,生成新的个体; ⑹ 由交叉和变异产生新一代的种群,返回到第2步。 ⑺ 返回步骤2。
遗传算法的步骤流程图如下:
遗传算法包括3个基本步骤:选择、交叉和变异。这些基本操作又有许多不同的方法。简要介绍如下。
1. 选择
选择是用来确定重组或交叉个体,以及被选个体将产生多少个子代个体。首先计算适应度:
①按比例的适应度计算 ②基于排序的适应度计算
适应度计算完毕后是实际的选择,按照适应度进行父代个体的选择。可以挑选以下的算法:①轮盘赌选择 ②随即遍历抽样③ 局部选择④ 截断选择 ⑤锦标赛选择
2. 交叉或基因重组
基因重组是结合来自父代交配种群中的信息产生的新的个体。根据个体编码表示方法的不同,可以有以下的算法
①实值重组 ②二进制交叉 3. 变异
变异是为了增加个体多样性,避免出现过早收敛。
正在阅读:
车辆路径问题11-29
哈尔滨市(全市)城镇职工基本养老保险和失业保险参保人数3年数据04-20
光伏行业消防设计说明07-04
输煤系统安装安全技术交底12-13
奥数-时钟快慢问题04-27
学生会部长个人工作总结范文范本08-04
隔爆水袋安装标准01-14
浅谈基督教在太平天国运动中的作用毕业论文09-23
数据结构设计报告总结05-16
小学生一年级语文下册看图写话快乐的植树节06-14
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 路径
- 车辆
- 问题
- 第16批符合道路运输车辆卫星定位系统标准及规范的车载终端
- 2019年九年级数学下册第二十七章相似27.3位似第1课时位似图形的概念及画法课后作业新版新人教版
- 2019版高考生物一轮总复习第5章第3节ATP的主要来源细胞呼吸课时练必修1
- 2019届高考生物复习三维设计必修2 遗传与进化
- 2002年成都外国语学校小升初“德瑞杯”知识竞赛数学试题+答案
- 现浇支架计算书
- 山东省潍坊市2016届高三上学期10月月考生物试题 Word版缺答案
- 超声引导经皮穿刺置管引流治疗肝脓肿的护理
- 2014年高考生物一轮复习课时达标检测:第十八章 第一讲 生态系统的结构
- 股权价值评估中流动性折扣的期权模型方法
- 三一重工收购德国普茨迈斯特
- 杭州装修顺序、所需材料及注意事项 - 图文
- 道家固精法之大锁龙功
- 印刷手提袋基本知识助手
- 华东师大版八年级历史上册第三单元新民主主义革命的兴起知识点归纳
- 解放思想改革创新推动中等职业教育又好又快发展
- 2016年浙江省高职单招单考《电子电工类》试题卷
- 同步精品课堂七年级语文上册专题02天的怀念(讲)(基础版,教师版)新人教版
- 物化复习题1
- 2019年2018年干部科科长试用期转正工作总结范文-优秀word范文(3页)