时变路网无能力约束车辆路径优化

开篇：润墨网以专业的文秘视角，为您筛选了一篇时变路网无能力约束车辆路径优化范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要： 讨论了一类时变路网下的无能力约束车辆配送路径优化问题，建立了基于时变路网的以配送总耗时最短为优化目标的无能力约束车辆配送路径优化模型。提出了基于实时Dijkstra算法的模型求解方法。数值算例表明考虑路网时变特性得到的优化配送方案将更加符合配送实际。

Abstract： In this paper， an uncapacitated vehicle routing problem based on time—dependent road network is discussed. A mathematic model the optimal object of which is to find the route schedule which has the minimum distribution time is established. The model solving method based on time—dependent algorithm is provided. The numerical example demonstrates that the optimal route schedule will be influenced by time—dependent road network.

关键词： 路径优化；车辆配送；时变路网；实时Dijkstra算法；无能力约束

Key words： route optimization；vehicle routing problem；time—dependent road network；time—dependent Dijkstra algorithm；uncapacitated

中图分类号：U49 文献标识码：A 文章编号：1006—4311（2012）27—0114—03

0 引言

在传统的车辆路径问题研究中，通常假定各个配送点之间为单一路径连接，在此基础上，在满足其他一些约束条件下寻求配送点的优化配送顺序。然而，在真实的路网结构下，各配送点之间并不一定是简单的单一路径连接，更多情况是连接各配送点的不是单一路径而是由多个不同路段组成的路网。此时，如果路网各路段在不同时间下车辆行驶不发生变化，可以简单认为在传统车辆路径问题中连接各个配送点之间的单一路径为各个配送点之间可能路径的最短路，则可以按传统车辆路径问题中假设各个配送点之间为单一路径（最短路）连接研究。但如果不同时刻不同路段车辆行驶速度会发生变化，则基于总配送时间最短的车辆路径优化问题中不同配送点之间简单假设为单一路径不再合适。一些文献研究车辆调度实时性问题[1—8]，但真实路网不同路段具有的不同实时性特性很难被配送点之间假设的单一路径实时性所表达，比如，同一时刻不同路段拥堵状态不一样，同一路段不同时刻拥堵状态不一样，而不同行驶路线抵达同一路段时刻不一致，从而导致该路段通过时间发生变化。文献[9]考虑了实时路况对车辆配送路径的影响，但该文献讨论的实际上是车辆从点到点的路径优化问题，当配送点为多个时，配送点的访问顺序会对配送点间路径选择产生影响。文献[10]讨论真实路网车辆路径优化问题，但该文献并未考虑路网时变特性。针对以上分析，本文将在复杂路网条件下，考虑不同路段时变路况对车辆配送路径的影响，研究无能力约束车辆配送路径优化问题。

1 时变路网无能力约束车辆路径问题建模

1.1 时变路网无能力约束车辆路径问题模型 令dij为路网中任意两点i点直达j点的距离，若路网中i、j两点无路径直达，则可用dij=+∞表达；vij（Ti）表示车辆Ti时刻从路网中任意两点i点直达j点的预估行驶速度（该速度函数可以由以往统计数据获得）；则tij（Ti）=■表示车辆Ti时刻从路网中任意两点i点直达j点的行驶时间，若路网中i、j两点无路径直达，则可用tij（Ti）=+∞表达，tij（Ti）为Ti的函数，这反映了路网的时变特性。令物流配送中心某车配送的客户集合为N（其中0代表物流配送中心），Ti为车辆到达i点的时刻，t■■（Ti），i，j∈N为Ti时刻从i点出发经路网到j点的时间最短路行驶时间（利用实时Dijkstra算法求解）。

定义决策变量xij（i，j∈N，i≠j），如果车辆为点i完成配送后下一配送点为j时（若车辆为完成配送任务返回配送中心，则将返回配送中心的这一行为当做一次配送任务），xij=1；否则，xij=0。则复杂路网时变无能力约束车辆路径优化问题数学描述如下：

min Z=■■t■■（T■）x■（1）

■xij=■xji，？坌j∈N（2）

■xij=1，？坌j∈N（3）

■■xij？燮U—1，？坌U？哿N＼{0}（4）

Tj=Ti+t■■（T■），when：xij=1（5）

式（1）表示数学模型的优化目标为配送时间最短。等式（2）为平衡条件，与等式（3）确保车辆在配送任务中为某需求点服务一次且仅为一次，若为配送中心，则表示车辆离开配送中心后完成配送任务仍回到配送中心。约束条件（4）确保配送回路通过配送中心。等式（5）为配送路径各配送点先后顺序时间逻辑，t■■（Ti）由时变路网Dijkstra算法求得。

1.2 时变路网Dijkstra算法 网络最短路问题中各边权重是一常量，但在本文所给网络中，各边权重为各边通行时间，但通行时间tij（Ti）为Ti的函数，因此，传统网络最短路求解方法不能直接用于本文任意两点（i到j）时间最短路t■■（Ti）的求解。通过分析传统Dijkstra算法求解最短路思想，本文提出图G=（V，E）中任意两点（i到j）时间最短路t■■（Ti）优化算法（实时Dijkstra算法）求解步骤如下：