The trade-off between fixed vehicle costs and time-dependent arrival penalties in a routing problem

•We propose a new VRPSTW model based on newly defined problem definition.•Branch-and-price with four novel subproblem techniques are developed for such model.•The VRPSTW model is compared to relevant variants over benchmark and real instances.•The VRPSTW outperforms all others in terms of cost and resource utilization.

This paper introduces the vehicle routing problem with soft time windows (VRPSTW) in which problem definition differs from ones previously defined in literature. Branch-and-price approach is employed, resulting in a set partitioning master problem and its new subproblem. Novel techniques are consequently developed to solve this new subproblem. Experimental results report the comparisons of these solution techniques under the branch-and-price framework. The VRPSTW solutions have further been compared to the state-of-the-art literature, signifying the superiority of the VRPSTW on this issue.