Research On The Bin Packing Problem With Time Windows

This paper introduces and studies the bin packing problem with time windows(BPPTW),which is a practical problem that is common in the logistics industry.The courier company needs to deliver the items from the distribution center to each customer every day.Before the delivery,it involves the problem of how to pack.When the items to be delivered contain the arrival time window limit,if the time window of Two items have not intersect.They can't be loaded into the same bin.At this time,the items can no longer be packed according to the traditional packing scheme.A reasonable packing plan must be designed for the packing problem with time windows.A reasonable packing solution not only saves transportation costs,improves distribution efficiency,but also further improves customer satisfaction.Suppose the distribution center has a number of items to be delivered and enough bins,and these items have different weights and delivery time windows,the goal is to select a set of bins with the lowest cost or the least number to pack all items.The total weight of items packed in the same bin must not exceed the weight constraint of the bin,and there must be a common point between the time windows of all items in the same bin.BPPTW is an extension of the bin packing problem.Since the bin packing problem is a NP-hard problem,BPPTW is also a NP-hard problem.Studying it can enrich the content of the combination optimization field and provide a benchmark for future scholars to study such problems.Studying BPPTW can also improve logistics distribution efficiency,thereby reducing transportation costs and increasing customer satisfaction.Therefore,studying BPPTW has important theoretical and practical value.This paper first considers the time windows into the one-dimensional bin packing problem,thus forming a new problem of one-dimensional packing problem with time windows(1DBPP-TW).After considering the mathematical model of the bin packing problem and the vehicle routing problem with time windows,a mathematical model was established for 1DBPP-TW.Firstly,this paper uses CPLEX developed by IBM to solve the model.Then,a Greedy-on-time-range heuristic algorithm(GTR)is proposed to quickly generate the initial feasible solution of the1DBPP-TW.Finally,an iterative local search algorithm(ILS)is used to further improve the quality of the solution.In this paper,a lot of instances are tested on CPLEX,GTR algorithm and ILS algorithm.The results show that CPLEX can only solve small scale instances,GTR algorithm can find a good initial solution for1DBPP-TW in a short time,ILS algorithm can further improve the quality of the initial solution.This paper continues to consider the time windows into the variable size bin packing problem,thus forming a new problem of variable size packing problem with time windows(VSBPPTW).Firstly,based on the 1DBPP-TW model,a mathematical model is established for VSBPPTW and CPLEX is used to solve the model.Then,the well-known best fit heuristic algorithm(BF)is used to generate the initial feasible solution for VSBPPTW.Finally,a shortest path decoder is supposed,and based on the shortest path decoder,developed the ILS algorithm to further improve the quality of the solution.In order to test the validity of the ILS algorithm,this paper uses the instances of variable size bin packing problem(VSBPP)in the literature(sample Set1 and Set2)to carry out experiments.The experimental results show that the ILS algorithm calculates the result of Set1 are inferior to the best variable neighbourhood search metaheuristic algorithm(VNS)for solving VSBPP in the literature,but the difference between VNS and ILS is very small.when the ILS algorithm solves the instances Set2,the calculation results of some test instances are better than the VNS algorithm,but the average result is inferior to the VNS algorithm.The ILS algorithm is an algorithm proposed for VSBPPTW,but it also shows higher performance when solving the VSBPP.The difference between the best VNS algorithm and ILS algorithm is small,which can prove the effectiveness of the ILS algorithm.Similarly,this paper continues to use the CPLEX,BF algorithm,ILS algorithm to solve the VSBPPTW instances.The results show that CPLEX can only solve small scale instances.The BF algorithm can find a good initial solution for VSBPPTW in a short time.The ILS algorithm can further improve the quality of the initial solution.Therefore,the conclusions drawn in this paper are as follows: GTR algorithm and BF algorithm can quickly generate the initial feasible solution for 1DBPP-TW and VSBPPTW.The ILS algorithm can further improve the quality of the initial solution.Although the ILS algorithm is an efficient heuristic algorithm proposed for 1DBPPTW and VSBPPTW,it also shows high performance when solving VSBPP.