路径规划问题介绍
概述
车辆路径问题(VRP)是运筹学里重要的研究问题之一。VRP关注有一个供货商与K个销售点的路径规划的情况,可以简述为:给定一个或多个中心(中心车库)一个车辆集合和一个顾客集合,车辆和顾客各有自己的属性,每辆车都有容量,所载的货物不能超过它的容量。
车辆路径问题的特性比较复杂,总的来说包含四个方面的属性:
(1)地址特性包括:车场数目、需求类型、作业要求。
(2)车辆特性包括:车辆数量、载重量约束、可运载品种约束、运行路线约束、工作时间约束。
(3)问题的其他特性。
(4)目标函数可能是总成本极小化,或者极小化最大作业成本,或者最大化准时作业
常见问题有以下几类:
(1)旅行商问题。
(2)带容量约束的车辆路线问题。
(3)带时间窗的车辆路线问题。
(4)收集和分发问题。
(5)多车型车辆路线问题。
(6)优先约束车辆路线问题。
(7)相容性约束车辆路线问题。
(8)随机需求车辆路线问题。
VRP定义
数学模型
有限连通图G(N,V):顶点集N={n_i |i=0,…,n} ,其中n_0代表出发点,其余n_i代表待经过的节点,任意两节点间多有一条边V_{ij}∈V,代表连接n_i和n_j的道路;
距离函数d:V→R: 函数值非负,代表路径距离;
可行解L={l_i }是G(N,V)中环路的集合,满足l_i∩l_j={n_0}, ∀i,j 且⋃_{l∈L}l=N;
问题的优化目标是使可行解中环路的总长度最小,即
衍生问题类型
问题类型列表
类型间的联系
问题类型分析
实际物流问题有如下的一般性约束条件:
多车型,容量限制,时间窗限制;
多车场:以伪多车场问题为主,可以拆分为多个单车场问题,真正的多车场问题要求订单和出发点不关联;
开放/封闭路径:前者常见于以运费为优化目标,后者常见于以距离为优化目标
收取货:一般是收货与取货互相独立的backhual模式;
分次投送:和车型相关,一般在车型相对小时有需求;
优化函数:以装载量为优化目标之一时,可能和主要优化目标互相独立,可单独做后处理;
- 点赞
- 收藏
- 关注作者
评论(0)