In public works companies, raw materials have to be transported by a fleet of heterogeneous trucks between sites for road building and levelling works. For some operations, in particular asphalt laying, some transportation requests may share a resource at their pickup or delivery locations (i.e. a loader machine or an asphalt paver). Hence, the routes that serve these requests have to be synchronized on this resource. This problem has been introduced as the full truckload pickup and delivery problem with resource synchronization (FT-PDP-RS).

The objective is to minimize a cost function composed of three terms: (i) fixed cost of using a truck, (ii) traveling cost and (iii) routes duration cost. The problem is solved with an Adaptive Large Neighborhood Search (ALNS) algorithm. An efficient feasibility procedure has been proposed to evaluate the feasibility of insertions.

We investigate the integration of a term that depends on routes duration in the cost function of the FT-PDP-RS. Integrating route duration minimization raises new difficulties, as “as early as possible” schedules are not optimal for a given set of routes. We present various approaches that have been proposed to handle this problem. The algorithms are evaluated on real life instances.