Abstract: The paper establishes 0-1 mixed integer programming models aiming at minimizing operation costs in the centralized commute service, which has characteristics as multi-destination, multi-automobile coordination and multi-routing shifts, and taking account of customer satisfaction, we can obtain the approximate minimum cost under different degrees of satisfaction. According to the complexity and large scale of the problem, a heuristic algorithm (class label algorithm) based on kNN is developed, which promotes and generalizes the method of path construction. The numerical results show that the model and algorithm proposed is effective and feasible.

Key words: centralized commute, vehicle routing and scheduling problem, minimizing costs, heuristic algorithm

摘要： 本文针对集中通勤接送服务业务流程中的车次分配与调度问题,建立了以最小化成本为目标的0-1混合整数规划模型,刻画了该问题所具有的多目标抵达地、多车协作、多行程车次等特征事实,同时考虑顾客满意度,以获得不同满意度下的近似最小成本。根据问题的复杂性和大规模性,设计开发了一种基于kNN思想的类标签启发式算法求解模型,拓展了构造路径的方法。算例数值结果表明,本文所设计模型和算法是有效性、可行的。

关键词: 集中通勤, 车辆路径与调度问题, 最小化成本, 启发式算法