  In this paper we study a long-haul truck scheduling problem where a path has
to be determined for a vehicle traveling from a specified origin to a specified
destination. We consider refueling decisions along the path, while accounting
for heterogeneous fuel prices in a road network. Furthermore, the path has to
comply with Hours of Service (HoS) regulations. Therefore, a path is defined by
the actual road trajectory traveled by the vehicle, as well as the locations
where the vehicle stops due to refueling, compliance with HoS regulations, or a
combination of the two. This setting is cast in a bi-objective optimization
problem, considering the minimization of fuel cost and the minimization of path
duration. An algorithm is proposed to solve the problem on a road network. The
algorithm builds a set of non-dominated paths with respect to the two
objectives. Given the enormous theoretical size of the road network, the
algorithm follows an interactive path construction mechanism. Specifically, the
algorithm dynamically interacts with a geographic information system to
identify the relevant potential paths and stop locations. Computational tests
are made on real-sized instances where the distance covered ranges from 500 to
1500 km. The algorithm is compared with solutions obtained from a policy
mimicking the current practice of a logistics company. The results show that
the non-dominated solutions produced by the algorithm significantly dominate
the ones generated by the current practice, in terms of fuel costs, while
achieving similar path durations. The average number of non-dominated paths is
2.7, which allows decision makers to ultimately visually inspect the proposed
alternatives.
