Abstract: Truck platooning uses connected vehicle technologies to reduce aerodynamic drag and improve fuel efficiency. 

While previous studies focus on centralized platooning planning, simultaneous consideration of system stability arising from individual truck preferences and trucks platooning multiple times during their trips has not been examined despite their practical relevance.

In this study, we fill this gap by investigating the problem of optimal truck platooning planning that maximizes social welfare subject to the most system stability characterized by the minimum number of blocking pairs.

We develop multiple mixed-integer linear programs (MILPs) to mathematically express this problem, along with multiple tailored algorithms including those based on Lagrangian relaxation and alternating direction method of multipliers (ADMM) to solve these MILPs. 

The MILPs and the solution algorithms are implemented in small hypothetical and larger regional networks. 

The computational results show superior performance of our tailored algorithms, particularly the ADMM-based algorithm.

Several operational insights are obtained, which lend support for simultaneous implementation of maximizing system stability and allowing multiple-time truck platooning in practice.