孙屹飞，蒋洪伟，张轶兰

(北京信息科技大学 信息管理学院，北京 100192)

0 引言

从现代物流管理系统的总体构成来看，路径规划问题是物流管理当中的核心问题之一。尤其在互联网电商交易和物流产业快速发展的今天，如何实时、动态、高效地调度车辆并合理规划行车路径一直是学界和业界共同关注的焦点。作为运筹学中一类典型的组合优化问题，经过国内外专家和学者半个多世纪的研究，路径规划问题已由早期的静态问题发展成为动态的、带复杂约束条件、多目标、多车场等类型的路径规划问题。

物流公司的路径规划问题一般表现为车辆路径问题[1](vehicle routing problem,VRP)，它的目标为最小化物流公司的运输成本，条件为每个客户点都只被访问一次，路线的开始和结束在同一仓库。最初的VRP是由Dantzig等[2]提出的。在此之后，VRP的许多变种和扩展被应用于各种场景。研究最广泛的2个扩展为：约束车辆的运力；带时间窗的VRP，一种客户必须在指定时间间隔内到达[3]的约束模型。之后，Erdogan等[4]提出了绿色VRP(green-vehicle routing problem，G-VRP)，一种电动汽车的车辆路径模型，其考虑到车辆的电池容量有限，以及必须在充电站充电，对于每次充电以及访问客户，都要考虑固定的服务时间。本文在基本的G-VRP基础上，还考虑了有限的车辆运输能力和客户时间窗，这是现实世界物流应用中最重要的限制因素。由于模型参数过多无法精确求解，我们设计了邻变域禁忌搜索算法(variable neighborhood search/tabu search, VNS/TS)用于模型求解。

1 电动汽车运输路径优化模型构建

1.1 参数定义

为了更加清晰准确地描述模型，本文对模型中使用到的符号进行如下定义：