配送车辆路径优化问题算法研究.pdf

第年第期商业经济
总第期
文章编号
配送车辆路径优化问题算法研究
刘北林高爽
哈尔滨商业大学黑龙江哈尔滨
摘要配送车辆路径优化问题是影响物流配送效率和成本的关键问题同时也是应用数学、计算机和物流配送领域
研究的热点问题。路径优化的算法主要有精确式和启发式两种。精确式算法可以求解小规模的配送路径问题当规
模增大时则很难求得满意结果。启发式算法主要有构造式、两阶段式、智能式算法其对于解决大规模的路径优化的问题
具有重要帮助。
关键词车辆路径精确算法启发式算法
中图分类号文献标识码
或式
一、问题描述及数学模型
或式
配送车辆路径安排问题—
其中目标式保证了总成本最小式为车辆的
是由和于年提出的一个典型的
容量约束式保证了每个客户点的运输任务仅由一辆车
组合优化问题是交通运输和物流配送领域的一个核心
来完成而所有的运输人物则由辆车共同完成式和
问题。即由多辆车将货物从一个或多个仓库送到多个地
保证每个客户能且只能被一辆车服务一次。
理上分散的客户如何安排车辆及其行驶路线使总的配
车辆路径问题流程图可以表示如下
送费用最小。
车辆路径问题的一般描述为有一个中心仓库拥有
辆车容量为有个客户点其需求为
⋯⋯且≤顶点集为⋯⋯求满足货运
需求的总最短行车路线。
根据不同的约束有多种不同类型从上述描述
中可知该问题是车辆数固定的单车场单车型非满载车
辆路径问题。用表示从点到点的运输成本其含义
可以是距离、费用及时间等设配送中心编码为客户编
码为⋯⋯定义变量
车辆由客户行驶到客户
流程图
! 否则
客户的任务由车辆完成二、问题分类

! 否则对的研究重点不同分类方式不同按任务持
建立数学模型征分类装货问题卸货问题装卸混合问题按任务性
质分类对弧服务问题对点服务问题混合服务问题
式
" " " 按车辆载货状况分类满载问题非满载问题按车场
数目分类单车场问题多车场问题按车辆类型分类
≤式
" 单车型问题多车型问题按车辆对车场的所属关系分
类车辆开放问题车辆封闭问题按已知信息的特征
式
" ! 分类有确定性和不确定性按约束条件分
类带能力约束的带时间距离约束的和带
式
" 时间窗口的按需求是否可切分分类可切分
的不可切分的按优化目标数分类单日标
式
" 问题多目标问题。
收稿日期
作者简介刘北林山东莱州人哈尔滨商业大学教授硕士生导师。研究方向商品学物流管理。
商业经济第年第期
在实际应用中一般可以分为以下几类带容继续建立其他的组直到所有节点都加入到组中。扫描法
量约束的车辆路径问题时间窗求解问题未必求得问题的最优解但能求得满意解。
约束的周期性配两阶段启发式算法
送的由多个仓库向顾客提供等于年提出了两阶段启发式算法
服务的开放式车辆路以改进构造算法求解的不足。该算法第一阶段常用构造
径问题随机需求车辆路径启发式算法来求得可行解第二阶段常用、
问题客户有物资需、、、等改善技术通过对点
要回收的。的调整向最优目标靠近每一步都产生新的可行解以代
替原来的解使目标函数得以改进一直继续到不能再改
三、算法研究
进