A new vehicle routing problem is modeled.
This paper solves core sub-problem that appeared in carrier collaboration.
An adaptive large neighborhood search is applied to a vehicle routing problem with profits.
Request selection and routing decision are handled simultaneously by a new mechanism.