王一瓯，王海鹏，2

(1.宾夕法尼亚州立大学工程学院，宾夕法尼亚 16801；2.南开大学经济学院，天津 300071)

基于双层规划的车辆路径问题研究

王一瓯1，王海鹏1，2

(1.宾夕法尼亚州立大学工程学院，宾夕法尼亚 16801；2.南开大学经济学院，天津 300071)

[摘要]针对城市交通堵塞的问题，提出了一种基于车辆路径问题(VRP)和使用者均衡问题(UE)的双层优化模型.在其上层是车辆路径选择问题的一种拓展，在其下层采用用户均衡交通分配模型对城市交通中的货运车辆和客运/通勤车辆进行第一原理性的数学刻画.结果表明：VRP-UE模型不但可以提出能够规避堵塞的交通方案，而且可以减少车辆本身可能带来的交通阻塞；采用双层优化模型可以显著降低车辆出行的时间成本.

[关键词]车辆路径；双层规划；城市物流

0引言

自1959年Dantzig和Ramser提出车辆路径选择问题以来[1]，该问题已成为最著名的组合优化问题之一.学术界在此领域取得了一系列的成果[2]，文献中提出了几个经典车辆路径选择问题的扩展，如随机车辆路径(SVRP)[3]、鲁棒车辆路径(RVRP)[4]以及带时间窗口的车辆路径选择问题(VRP-TW)[5].

交通堵塞已经成为影响城市发展和人民生活的重要问题之一.学术界对存在交通堵塞情况下的车辆出行问题的研究也已取得一些成果，如文献[6]认为物流车辆经过不同节点时，所产生的时间成本不但与两节点间的距离有关，而且与此时的时间相关(TD-VRP)，因而交通拥堵可以由动态变化的时间成本来描述.而文献[7]采用的模型结构对本文最具启发性，该文献认为：在城市物流环境下，一方面就车辆路径选择问题的数学描述而言，物流车辆经过不同节点之间所产生的时间成本应由文献[8]中的仿真模型进行描述；……