An exact method to solve the flex-route transit operational planning problem considering energy consumption
研究了考虑能耗的灵活路线公交运营规划问题，提出分支定价算法精确求解，实验表明该算法在解质量和计算效率上优于商业求解器和常用启发式算法。
In recent years, the flex-route transit (FRT) has become increasingly popular due to its convenience, especially in scenarios where transportation demands are sparse or dispersed. However, due to growing concerns about greenhouse gas emissions, reducing the energy consumption of vehicle travel has emerged as a critical issue. To this end, this paper aims to address the flex-route transit operational planning problem with energy consumption (FRTOPP-EC) through a mixed-integer programming (MIP) formulation. The objective is to minimize the energy consumption of all deployed vehicles by optimising their routes. Given the computationally intractable nature of FRTOPP-EC, we develop a branch-and-price (BAP) algorithm to solve it exactly. To tackle the pricing problem efficiently arising in the proposed algorithm, a tailored label correcting algorithm (LCA) is designed. Computational experiments are conducted using benchmark instances derived from a real-life system of FRT. The results indicate that our BAP algorithm outperforms the commercial solver (e.g. CPLEX) in terms of solution quality, the size of problems it can solve, and computational efficiency. Furthermore, comparative results with the commonly used heuristic insertion algorithm (HIA) underscore the superior effectiveness of our BAP algorithm. Finally, extension experiments are discussed to offer managerial insights for employers.