One key role along green supply chain is the distribution center which has the responsibility to deliver the commodities to the customers and collect the end-used products back to the center for further process. This activity requires a distributor to determine how many vehicles with what sizes along which routes to deliver commodities so that the demands from all customers will be satisfied within customers’ available time with minimum operation cost. This problem can be classified into a vehicle routing and scheduling problem with multiple vehicle types and service time windows. In practice, the complexity of the problem requires a structural model to facilitate general analysis and applications. However, also because of its complexity, an efficient solution procedure is equivalently important. Therefore, in this study, we have first developed a model for a distribution center to support the decisions on vehicle types and numbers; as well as the routing route and schedule so that the overall operation cost will be minimized. Since this model of vehicle routing and scheduling problem with multiple vehicle types and multiple time windows (VRSP-MVMT) is a nondeterministic polynomial time (NP)-hard problem, we have developed a genetic algorithm (GA) for efficient solution. The efficiency and accuracy of the algorithm will be evaluated and illustrated with numerical examples.
TopIntroduction
In 1959, Dantzig and Ramser investigated the truck dispatching problem (TDP) and were considered the pioneers of the vehicle routing problem (VRP). VRP considers a given vehicle with limited or unlimited capacity which deliveries (homogenous) products from a distribution center to a set of customers with known demands. For a green supply chain, this activity is in particular emphasized by its function of recycling. The delivering planning process must take into consideration the best possible route to satisfy these customers and the environmental impact.
The VRP has many characteristics, including the information of the demand, vehicle fleet, crew requirement, and data requirement. All of these further complicate an already complicated problem, with a multitude of solutions being put forward. VRP is like the intermediate state between sophisticated theory and the real world. On one hand, we have many mathematical models proposed by many scholars to deal with different requirements. On the other hand, they have been applied to many different practical situations such as postal delivery, transportation of the handicapped, product distribution, and others. Vehicle routing problem plays an important role in green logistic management, because money distribution and green legislation go hand in hand with physical distribution. Purchasing vehicles and planning the routes of those vehicles are the most important factors affecting the cost of a physical distribution. Therefore, the number of vehicles a company needs and how to arrange the vehicle routing remain the main issues for a distribution company. In this study, we will concentrate on these two problems.
The 3R (Recycling, Reuse, and Reduction) activities in the green market keep increasing, and as a result not only the original delivery and dispatching of forward distribution need to be considered, but also the collection and recycling of reverse routing have to be planned. The prime consideration for finding an answer to the VRP is to minimize the total traveling cost and at the same time satisfy the demands of the customers. Over the years, many methods have been developed.
In this study, we investigate the combined vehicle routing and scheduling problem (VRSP). VRSP can be thought of as routing problems with the additional constraints of various activities having to be carried out within a certain time limit. However, from our observations of the operations of distribution companies, the existing model with a single time window allowance is insufficient for dealing with a competitive market. Therefore, a more flexible and more realistic model is needed for a wider range of applications.
Based on the above motivation, this study considers a vehicle routing and scheduling model with multiple vehicle types and multiple time windows (VRSP-MVMT). We will determine how to dispatch a limited number of multiple vehicle types from a distributional center to a set of customers and return to the center. Each of these customers will be offered two time intervals for receiving the services. Because each customer can set two time intervals for receiving the services, there are four possible time pairs that occur, and time windows combination cost is incurred accordingly. The first time pair (1,1) means time window 1 of former customer combines time window 1 of next customer. The second time pair (1,2) means time window 1 of former customer combines time window 2 of next customer. The third time pair (2,1) means time window 2 of former customer combines time window 1 of next customer. The final time pair (2,2) means time window 2 of former customer combines the time windows 2 of next customer. The vehicles will have to return to the center after delivery. This study will investigate the minimum operation cost including vehicles dispatched cost, traveling cost, and time window combination cost.
Although VRSP-MVMT is a relaxed variation of VRSP, the problem is not easy to formulate and remains difficult to solve. When the size of the problem increases, the solution time increases exponentially. Therefore, apart from developing a mathematical model, we shall propose an efficient solution procedure in this study.
In summary, the main purposes of our study can be outlined as follows.
- (1)
To develop a model of VRSP-MVMT, and investigate its properties.
- (2)
To transform the model into a simple and computational form.
- (3)
To develop an algorithm for the proposed model and obtain a near-optimal solution at a reasonable computation time.
- (4)
To evaluate the proposed model and algorithm on both accuracy and efficiency with existing benchmark problems.