路线选择系统、路线选择方法和路线选择程序

摘要

提供一种用于用合理计算量获得多对到路线搜索过程的技术。在使用指示出发点和目的地点的信息作为请求时，公式表达为混合整数规划(MIP)问题，其中目标函数是“使通过将用于所有请求的实际所需时间除以最短所需时间而获得的所有值中的最大值最小”。通过在从初始状态逐渐和反复添加有希望路线的过程中，求解MIP问题来阻止候选路线数目的激增。也通过使用在迭代结束时的实际路线来搜寻新路线，优先搜寻具有高效用值的路线作为备选路线。这时去除具有比当前最佳解更大的最小成本的任何路线和在先前迭代中添加的任何未用路线作为无希望路线。通过在更新路线候选时保持在先前迭代期间使用的路线，先前迭代的解可以用作MIP问题中的初始值，并且减少计算时间。