Modeling and Solving the Traveling Salesman Problem with Speed Optimization for a Plug-In Hybrid Electric Vehicle
研究了插电式混合动力汽车在路线中同时优化各路段平均速度和运行模式的旅行商问题变体，提出了两种混合整数非线性规划模型及分支切割算法，实验表明该方法能有效求解现实规模实例并显著节能。
This paper investigates a variant of the traveling salesman problem (TSP) with speed optimization for a plug-in hybrid electric vehicle (PHEV), simultaneously optimizing the average speed and operation mode for each road segment in the route. Two mixed-integer nonlinear programming models are proposed for the problem: one with continuous speed decision variables and one with discretized variables. Because the models are nonlinear, we propose reformulation schemes and introduce valid inequalities to strengthen them. We also describe a branch-and-cut algorithm to solve these reformulations. Extensive numerical experiments are performed to demonstrate the algorithm’s performance in terms of computing time and energy consumption costs. Specifically, the proposed solution method can efficiently solve instances with a realistic number of customers and outperforms the benchmark approaches from the literature. Integrating speed optimization into the TSP of a PHEV can lead to significant energy savings compared with the fixed-speed TSP. In addition, the proposed model is extended to investigate the impact of the presence of charging stations, which makes the problem harder to solve but has the potential to further reduce energy consumption costs. Funding: F. Wu gratefully acknowledges the support of the National Natural Science Foundation of China [Grant 72271161]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.0247 .