Maximizing profit for vehicle routing under time and weight constraints

Utilizing an empty backhaul vehicle on its way back to its domicile after a normal delivery trip has attracted many logistics carriers and third party logistics companies in the current revenue-hungry economy. In this paper, a backhaul vehicle routing and delivery scheduling problem is studied with the objective of maximizing the total business profit that the vehicle generates during its backhaul trip. The problem has two constraints: the time constraint for the entire backhaul trip and the capacity constraint of the vehicle. It also has two integral parts, vehicle routing and delivery scheduling. An analytical model is developed for this problem, which turned out to be NP-hard to solve due to its complexity. Therefore, the model is decomposed into two parts: finding feasible routes and generating the best delivery schedule for a given route. A heuristic solution is developed to solve the model, in which a genetic based algorithm is used to find the best known feasible route and a linear programming model is used to find the best delivery schedule for a given route. The two solution parts are integrated seamlessly and the best solution is found after iterating through the routes in search for improvement. Numerical study of various sizes of problems has demonstrated that relatively large size of problems could be solved with good solution quality in a reasonable time which is acceptable in real world practice. Third party logistics or other companies could use the solution method provided in this study to utilize their unused vehicle capacity in certain time periods, such as during a backhaul trip, which might be otherwise ignored.