Mobility allowance shuttle transit (MAST) services: MIP formulation and strengthening with logic constraints
Mobility allowance shuttle transit (MAST) services: MIP formulation and strengthening with logic constraints
复制标题
DOI：
10.1016/j.ejor.2006.12.030
复制
发表时间：
2008-03
期刊：
影响因子：
--
通讯作者：
L. Quadrifoglio;M. Dessouky;F. Ordóñez
中科院分区：
文献类型：
--
作者：
L. Quadrifoglio;M. Dessouky;F. Ordóñez
我们研究了一种混合运输系统，称为机动性允许穿梭运输(MAST)，其中车辆可能偏离由几个强制检查站组成的固定路径，以服务于分布在适当服务区域内的需求。提出了一种求解桅杆类系统静态调度问题的混合整数规划(MIP)方法。由于该问题是NP难的，我们通过对乘客行为的合理假设，开发了逻辑割集。这些约束的目的是通过从原始可行域中去除无效解来加速搜索最优解。实验结果表明，该方法是有效的，部分实例的CPU求解时间减少了90%。
We study a hybrid transportation system referred to as mobility allowance shuttle transit (MAST) where vehicles may deviate from a fixed path consisting of a few mandatory checkpoints to serve demand distributed within a proper service area. In this paper we propose a mixed integer programming (MIP) formulation for the static scheduling problem of a MAST type system. Since the problem is NP-Hard, we develop sets of logic cuts, by using reasonable assumptions on passengers’ behavior. The purpose of these constraints is to speed up the search for optimality by removing inefficient solutions from the original feasible region. Experiments show the effectiveness of the developed inequalities, achieving a reduction up to 90% of the CPU solving time for some of the instances.