Abstract Coordination for truck platooning refers to the active formation of a group of heavy‐duty vehicles traveling at close spacing to reduce the overall truck operations costs. Conventionally, this coordination is achieved by optimizing various truck‐related parameters, such as schedules, velocities, and routes, based on an objective function that minimizes a certain cost, for example, fuel usage. However, prevalent algorithms for the coordination problem are typically integer‐constrained, which are not only hard to solve but are not readily scalable to increasing fleet sizes and networks. In this paper, to overcome these limitations, we propose a centralized formulation to optimize the truck parameters and solve a multidimensional objective cost function including fuel, operation time costs and preferential penalty. Furthermore, to improve the scalability of our proposed approach, we propose a decentralized algorithm for the platoon coordination problem involving multiple fleets and objectives. We perform both theoretical and numerical studies to evaluate the performance of our decentralized algorithm against the centralized solution. Our analysis indicates that the computation time of the proposed decentralized algorithms is invariant to the increasing fleet size, at the cost of a small relative gap to the optimum cost given by the centralized method. We discuss these results and present future directions for research.