A Vehicle Routing Problem with Time Windows Subject to the Constraint of Vehicles and Good’s Dimensions

A vehicle routing problem (VRP) can be defined as a problem of finding the optimal route with the goal to minimize the travel distance, time, and cost used in a distribution process. A vehicle routing problem with time windows also known as a Time Window Priority Model (TWPM) prioritizes time windows in the mathematical modelling so that vehicles would not delay at any point during the distribution process. There exist few literatures discussing a TWPM subject to carrying capacity. They only consider the volume of vehicle container and the volume of items being carried, arbitrary using 90% of the vehicle’s capacity which causes a large unused capacity. The utilization of capacity which is defined as the ratio the actual weight of the items being transported to the maximum weight of the total items with full capacity, is an important factor for an efficient transportation.  We believe that the utilization of the vehicle’s capacity can be increased when taking into account the actual dimensions of goods, such as their lengths, widths, and heights, as well as the dimensions of the vehicle’s containers. In this study, we consider a 3-dimensional loading constraints i.e. the length, width, and height of both items and vehicles. Based on the results of the study, it can be concluded that taking into account the actual dimensions of items and containers in the capacity constraint increases the utilization of vehicles as well as reduces the total travel distance. Moreover, in some cases the total number of routes can be reduced.

Capacity loading constraint; Three-dimensional loading constraint; Time window priority model; Vehicle routing problem;

     One of the core elements of supply chain management is managing the transportation process (Hugos, 2003; Young and Sook, 2000). Transportation or distribution can be optimized by implementing a vehicle routing problem (VRP), which is described as a problem designing an optimal delivery or collection routes from one or several depots to a number of geographically scattered cities or customers, subject to side constraints (Laporte, 1992; Cordeau et al., 2007). The main scope of the problem involves finding a set of vehicle routes (usually not fixed) that optimally visit a specific number of clients or nodes, concerning several constraints (Trachanatzi et al., 2020).

       Some previous studies have been carried out to solve VRPs considering time window constraints. Wang and Wen (2020) developed an LC-2EHVRP model with a mixed timewindow, simultaneously considering economic cost, environmental issues (carbon emissions), and customer satisfaction for 3PL in cold-chain logistics and obtained an optimal solution to deal with it. Comert et al. (2017) proposed a hierarchical approach to solving Vehicle Routing Problem with Time Windows (VRPTW) that consists of two stages: clustering and routing. In the clustering stage, customers are assigned to vehicles using three different clustering algorithms: K-means, K-medoids, and DBSCAN, with the controlling capacity of each cluster. In the routing stage, a traveling salesmen problem (TSP) is solved based on a Mixed-Integer Liner Programming (MILP) model that aims to minimize total waiting and travel times.

        Kong et al. (2013) developed a VRP mathematical model called the Time Window Priority Model (TWPM). The model includes time window constraints (i.e., clients' opening and closing hours) to ensure that vehicles arrive within specific intervals during the distribution process. The model also includes another constraint on carrying capacities. The vehicle capacity constraint only considers the volume of transported items and the vehicle container volumes, arbitrarily assigning 90% of the vehicle capacity, which causes a large number of unused capacities. As such, it is necessary to consider the dimensions of both the transported items and vehicle’s containers in order to define the capacity constraint, thereby increasing the container’s capacity utilization. To do so, we developed a VRP with time windows subject to capacity constraints, taking into account the actual dimensions of both items and vehicles. We assumed that the problem is static and deterministic. It was also assumed that vehicles were homogeneous and the container shapes were identical. The orientation of transported items was fixed, and the vehicle routing was dedicated to a pick-up service. The remainder of the paper is as follows: Section 2 discusses the methods and solution approaches to the problems. The results and discussion are presented in Section 3, with the conclusions and further research being discussed in Section 4.

      Based on the results of mathematical calculations and analyses, several conclusions can be drawn: (1) This study aimed to TWPM propose a model that considered the actual dimensions of items and containers in the capacity constraints, namely, TWPM with 3D loading constraints. The TWPM mathematical model with 3D loading constraints can solve the trip-route determination problem. The constraints that must be considered include the time window constraint for each vendor as well as the dimensions of transport items and vehicle container constraints (length, width, and height) of each vendor; (2) The results of the TWPM mathematical model with 3D loading constraints were proven to increase the capacity utilization of vehicle containers and reduce the total travel distance; (3) This study assumed that vehicles used to solve the routing problem are homogeneous; hence, routing using a heterogeneous vehicles should be considered in future research.

Beheshti, A.K., Hejazi, S.R., Alinaghian, M., 2015. The Vehicle Routing Problem with Multiple Prioritized Time Windows: A Case Study. Computers & Industrial Engineering, Volume 90, pp. 402–413

Comert, S.E., Yazgan, H.R., Sertvuran, I., Sengul, H., 2017. A New Approach for Solution of Vehicle Routing Problem with Hard Time Window: An Application in A Supermarket Chain. Sadhana, Volume 42(12), pp. 2067–2080

Cordeau, J.F., Laporte, G., Savelsbergh, M.W., Vigo, D., 2007. Vehicle Routing. In: Handbook in OR & MS 2007, Barnhart and Laporte (eds.), ELSEVIER, Philadelphia

Hifi, M., Kacem, I., Negre, S., Wu, L., 2010. A Linear Programming Approach for the Three-Dimensional Bin-Packing Problem. Electronics Notes in Discrete Mathematics, Volume 36(2010), pp. 993–1000

Hugos, M., 2003. Essentials of Supply Chain Management. USA: John Wiley & Sons, Inc.

Kim, T.K., 2015. T Test as A Parametric Statistic. Korean Journal of Anesthesiology, Volume 68(6), pp. 540–546

Kong, J., Jia, G., Gan, C., 2013. A New Mathematical Model of Vehicle Routing Problem Based on Milk-Run. In: International Conference on Management Science and Engineering 20th Annual Conference Proceedings

Laporte, G., 1992. The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms. European Journal of Operational Research, Volume 59(3), pp. 345–358

Martello, S., Pisinger, D., Vigo, D., 2000. The Three-Dimensional Bin Packing Problem. Operations Research, Volume 48(2), pp. 256–267

Trachanatzi, D., Rigakis, M., Marinaki, M., Marinakis, Y., 2020. A Firefly Algorithm for the Environmental Prize Collecting Vehicle Routing Problem. Swarm and Evolutionary Computation, Volume 57, 100712

Tsai, R.D., Malstrom, E.R., Kuo, W., 1993. Three Dimensional Palletization of Mixed Box Sizes. IIE Transactions, Volume 25(4), pp. 64–75

Wang, Z., Wen, P., 2020. Optimization of a Low-Carbon Two-Echelon Heterogeneous-Fleet Vehicle Routing for Cold Chain Logistics under Mixed Time Window. Sustainability, Volume 12(5), pp. 1–22

Young, H.L. Sook, H.K., 2000. Optimal Production-Distribution Planning in Supply Chain Management using a Hybrid Simulation-Analytic Approach. In: 2000 Winter Simulation Conference Proceeding, Orlando, FL, USA