旅行商问题建模.docx
需积分: 10 133 浏览量
2021-04-15
11:35:11
上传
评论
收藏 32KB DOCX 举报
外卖配送员路径规划问题属于带时间窗及取送货的 VRP，这类问题均起源与 TSP，TSP 简单
来说就是：一个人为了完成自己的任务，需要从起点无重复的经过 N 个任务点，为此他需
要在出发前为自己设计一条合适的路线，使得这条路线是所有路线中用时最短的一条。但
是由于外卖的特殊性，所以在实际的配送中，对时间的要求更高，约束也更加严格，同时
外卖配送在完成配送任务后不用回到起始位置。
以美团外卖为例，不考虑其他第三方平台配送以及商家自行进行配送的情况下，一个外卖
订单的流程：
为了更加直观的描述，建立了外卖配送结构图。如图 1 所 示，以一个配送员与三个配送任
务为例，配送员从起点开始，先 去 2 号商家取货，取完货后接着去 1 号商家取货，然后为
4 号顾客
送货，之后去 3 号商家取货，最后一次完成 5 号和 6 号顾客的送
货，当完成所有商家节点配送任务后不需要返回起点。 图 1 外卖配送结构图
2.2 模型假设
为了更好的进行研究和构建模型，首先对外卖员配送路径进行以下假设：
（1）外卖员在接单时的接单数量不会超过车辆的称重，所有路径的配送距离都在系统要求
的公里数内
（2）外卖员的配送位置、商家以及客户的坐标都是已知
（3）
为更好地对问题进行研究，便于模型的建立和求解，对该问
题做出以下的假设: （1）由一名配送员为多个商家及对应的顾客服务，且商家和
顾客的位置坐标、停留时间和时间窗要求都是已知的； （2）配送员接单时不会超出车辆
的最大载重量和最大行驶
距离；（3）配送员从起始位置出发后，必须先前往某个商家，才能
给对应的顾客送餐，完成所有的配送任务后不用回到起始位置； （4）每单配送任务中商
家与顾客都是唯一对应关系，不存在
一个商家对应多个顾客和一个顾客对应多个商家的情况； （ 5）每个节点都有时间窗要求，
配送员如果不能在规定时间
内完成取送货任务时会有一定的惩罚成本； （6）配送车辆匀速行驶，忽略配送过程中的
路况问题以及配
送员的自身问题。
同时假设骑手对该条送餐路径足够熟悉
假设时间从中午 11 点开始，到下午 1 点，因为这个时间段的用餐人数是最为集中的
评论0
最新资源