刘天虎，许维胜，吴启迪

（同济大学 电子与信息工程学院，上海201804）

车辆路径问题（vehicle routing problem，VRP）是在满足一定约束条件下使适宜的行车路径达到既定的目标（如费用最小、耗时最短、行程最短等）.而带时间窗的车辆路径问题（vehicle routing problem with time windows，VRPTW）则是在VRP问题上加上了访问需求的时间窗口.Desaulniers等[1]研究了具有等待成本的多资源站的VRPTW问题，得到了最优解.Qureshi等[2]提出了在软时间窗约束下的VRP搜索的精确最优解决方案，从而识别最短的行驶路径，控制最小的成本消耗.Ghoseiri等[3]对多目标的VRPTW搜索问题进行了系统研究，利用目标规划及遗传算法得到了最优路径解.为了求解VRPTW问题，过去的研究中最常用的算法有禁忌搜索算法[4]、插入启发式算法[5]、粒子群算法[6]、人工智能算法[7]、拉格朗日松弛算法、近似算法等，本文在以上研究的基础上，利用混合遗传算法（hybrid genetic algorithm，HGA）[8]研究当医疗救援站仅有1个时，如何调度多辆医疗救援车辆的最优VRPTW问题.

1 问题描述

突发灾害事件的发生往往对医疗救援活动提出急迫的需求，如何在有限的资源条件下实现最有效的救援问题越来越引起人们的重视，特别是如发生地震这样的灾害事件，要求医疗急救资源迅速做出响应，这就需要各个医疗救援站对救援车辆进行合理调度，然而一个医疗救援站不可能为所有的灾害点提供救援服务，而且每个灾害点在不同阶段的医疗救助需求也可能不同.本文需要解决以下2个问题：①当发生突发灾害事件时如何最小化救援的总成本……