An Integer Programming for a Bin Packing Problem with Time Windows: a Case Study of a Thai Seasoning Company

This study aimed to improve the transportation management of a case study company which produced seasoning powder. Recently, they had two main problems in logistics department: high transportation cost and long vehicle scheduling time. Thus, the objectives of this study were to reduce transportation cost and scheduling time. Due to the delivery in Bangkok and metropolitan area, this problem became the vehicle routing problem with time windows. Then, we proposed a three phases-heuristics which composed of clustering, vehicle allocation and vehicle routing. In the first phase, we applied mapping to visualize the locations of customers. Then, the experts determined how to cluster the customers. The benefit of this phase was to reduce the problem size. In the second phase, the customers in each zone were allocated to the truck. Due to the distribution in Bangkok and metropolitan, there was a time windows constraint for some customers. Hence, we formulated the integer programming to minimize the number of vehicles used since the company outsourced the transportation to the third party logistics (3PLs) or the logistics providers who charged the fixed cost per truck. Hence, the problem became a bin packing problem with time windows constraints. Then, we used Lingo 6.0 and solver function in Microsoft Excel to solve the problem. Finally, in the third phase, the logistics providers who had experience of the traffic and roads solved the routing problem of each truck regarding the time windows constraint of the customers. The result showed that the monthly transportation cost was reduced by 23% or 37,650 baht per month and computational time was reduced by 67%.