Algorithms on a Path Covering Problem with Applications in Transportation

Given a road network, a source, a destination and K platoon paths, our aim is to reach the destination in a maximum given time using the benefits of traveling along platoons. We consider two objective functions (maximize the total time spent as a member of a platoon or minimize the time traveled without platoons) and for each such objective function, we have two scenarios: in the first one we are given the moments when platoons start to travel, while in second version we can decide these moments. We show several NP-hardness results as well as a dynamic-programming polynomial time algorithm (for the scenario in which the starting times are given). Then we describe an approximation algorithm with a factor 1/c that has running time exponential in K/c, with \(1\le c\le K\) .