Modeling and Solving the Traveling Salesman Problem with Speed Optimization for a Plug-In Hybrid Electric Vehicle

Fuliang Wu (), Yossiri Adulyasak () and Jean-François Cordeau ()
Additional contact information
Fuliang Wu: HEC Montréal, Montréal, Québec H3T 2A7, Canada
Yossiri Adulyasak: HEC Montréal, Montréal, Québec H3T 2A7, Canada
Jean-François Cordeau: HEC Montréal, Montréal, Québec H3T 2A7, Canada

Transportation Science, 2024, vol. 58, issue 3, 562-577

Abstract: 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.

Keywords: plug-in hybrid electric vehicle; traveling salesman problem; speed optimization; branch-and-cut (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2023.0247 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:58:y:2024:i:3:p:562-577

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().