Profitable Pickup and Delivery Problem with Time Windows and Compatibility Constraints

Due to the emergence of online freight marketplaces, shippers can release freight requests, and logistics companies can share and trade excess freight capacity on the online platforms. In practical urban logistics, because some goods cannot be loaded with others, developing the routes and loading plans is a complex problem. In this paper, a new mathematical model named is proposed to model this real problem. To solve this problem, this model is decomposed into a master problem and pricing subproblem in a column generation framework and develop a branch-and-price algorithm. In the algorithm, the master problem is solved by CPLEX solver and a labeling algorithm is proposed to solve the subproblem. The efficiency of this algorithm is evaluated by a comprehensive test bed of instances and compared with using only CPLEX solver. Result shows the algorithm is capable of overcoming this complex problem and significantly outperforms using only CPLEX.