A Multi-Vehicle, Multi-Factory Assignment Problem: A Case of Coca-Cola Bottling Company at Ahinsan and Spintex-Ghana

Show more

1. Introduction

In vehicle usage, there are two important choices: The choice of the vehicle that will be used for transportation and, the route to be traveled. The use of mathematical programming is needed to provide an optimal decision because these choices have important implications for transportation planning and policy-making [1]. Transportation problem from most literature assumes the use of a single-vehicle type. This shows either a Vehicle Routing Problem (VRP) or Multi-Factory Vehicle Routing Problem (MFVRP) [2] [3]. This assumption disregards any decision pertaining to the real application where there is diversity in the types of vehicles in a particular transportation fleet. This paper looks at how each type of vehicle is selected for each required shipment after the optimal routing.

In decisions regarding the use of vehicles in a transportation fleet, one key decision is the choice of vehicle [1]. The existence of different types of vehicles opens up the possibility of selecting optimal choices on the type of vehicles to use.

The involvement of different types of vehicles in a transportation fleet is believed to render an economical approach for public-transport [4]. Public-transports (transits) involve lots of stopovers with constant changes in the load (passengers). According to [5], a mixed fleet with multi-compartment and single-compartment vehicle is better than a single fleet vehicle, especially in grocery distribution. The distribution of groceries also involves stopovers with decrease in load as groceries are offloaded to consumers. This work considers the use of heterogeneous vehicle fleet in product haulage where there are no stopovers and no movements between distributors with no changes in the initial carrying loads of the vehicle. Again, vehicle type scheduling mostly results in minimal transportation fleet size with minimum operational cost [6]. Reference [7] also concluded that sometimes transportation cost depends on factors such as the capacity of the vehicle and the amount transported. Vehicle types are distinguished by several parameters according to [8]. Such parameters depend on the vehicle, maintenance cost, performance, and fuel consumption. Transportation vessel capacity affects transportation cost, according to [9] and the choice of the vehicle depends on the factor such as the purpose and road condition of the road [10].

A transportation problem can also be solved as a two-tiered transportation problem [11]. The idea is to solve each transportation problem based on each vehicle type on each tier.

2. Problem Definition and Formulation

The problem is formulated to optimally select the type of vehicle to transport different products to several depots. In finding an optimal solution to a MFVRP emphasis is not given to the type of vehicle used which in many real cases is a vital decision variable [2] [3]. Companies such as the Coca-Cola bottling company have a heterogeneous transportation fleet. Therefore, the type of vehicle used was taken into account and then formulated a Multi-Factory Vehicle-Type Routing Problem (MFVTRP). Consider a company that produces more than one product from two factories (A and B) as shown in Figure 2 and supplies 105 independent scattered distributors Figure 1. Since the company uses various types of vehicles, this work seeks to find a feasible minimum transportation cost in which 1) each vehicle capacity is not exceeded; 2) the demand at the distributors is responded to; 3) the vehicle commutes in a sequence of trips, starting and ending at the same factory.

Figure 1. Locations of all distributors.

Figure 2. Two factories supply all distributors.

Assumption of the model:

1) demand is estimated ahead of production and must be met at all time.

2) products occupy similar volume.

This work decides on the best route to use in transporting the Coca-Cola beverage to the 105 distributors. Again, from Figure 2 each distributor can be supplied from the two factories (A and B). In view of this we can select an optimal route depending of the best factory to supply a distributor.

2.1. The Model Formulation

2.2. Optimization Model

Using the sets, variables and parameters definition above, the optimization model is formulated as;

Objective function

Minimize cost (Z): F_{1} (1)

${F}_{1}={\displaystyle \underset{{v}_{1}.{f}_{1},{d}_{1},{t}_{1}}{\overset{V,F,D,T}{\sum}}{\nu}_{fd}^{v,f,d}\cdot {N}_{vfd}^{t,v,f,d}}$ (2)

Constraints

Equations (3)-(16) are the model constraints. These constraints set conditions for the model variables.

$\forall {t}_{0,\cdots ,T,p,f,m}:{A}_{prod}^{f,m,p,t}\le {\eta}_{cap}^{m,f,p}\cdot {\sigma}_{act}^{f,m,t}$ (3)

$\forall {t}_{0,\cdots ,T,f,p}:\underset{{w}_{1},{v}_{1}}{\overset{W,V}{{\displaystyle \sum}}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{A}_{tfw}^{f,p,v,w,t}=\underset{{m}_{1}}{\overset{M}{{\displaystyle \sum}}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{A}_{prod}^{f,m,p,t}$ (4)

$\forall w,p,{t}_{0}:{A}_{ware}^{w,p,0}=\underset{{f}_{1},{v}_{1}}{\overset{F,V}{{\displaystyle \sum}}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{A}_{t,f,w}^{f,p,v,w,0}$ (5)

$\forall w,p,t:{A}_{ware}^{w,p,t}={A}_{ware}^{w,p,t-1}-\underset{{d}_{1},{v}_{1}}{\overset{D,V}{{\displaystyle \sum}}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{A}_{twd}^{w,p,v,d,t}+\underset{{f}_{1},{v}_{1}}{\overset{F,V}{{\displaystyle \sum}}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{A}_{tfw}^{f,p,v,w,t}$ (6)

$\forall {t}_{0},w:\underset{{p}_{1}}{\overset{P}{{\displaystyle \sum}}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{A}_{ware}^{w,p,t}\le {S}_{cap}^{w}$ (7)

$\forall {t}_{1,\cdots ,T,w,p}:\underset{{d}_{1},{v}_{1}}{\overset{D,V}{{\displaystyle \sum}}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{A}_{twd}^{w,p,v,d,t}\le {A}_{ware}^{w,p,t-1}$ (8)

$\forall p,d,{t}_{1,\cdots ,T}:\underset{{w}_{1},{v}_{1}}{\overset{W,V}{{\displaystyle \sum}}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{A}_{twd}^{w,p,v,d,t}={\delta}^{d,p,t}$ (9)

$\forall v,w,d,{t}_{1,\cdots ,T}:\underset{{p}_{1}}{\overset{P}{{\displaystyle \sum}}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{A}_{twd}^{w,p,v,d,t}\le {N}_{vfd}^{v,t,f,d}\cdot {\nu}_{cap}^{v}$ (10)

$\forall v,{t}_{1,\cdots ,T},f:V{F}^{v,t}=\underset{{d}_{1}}{\overset{D}{{\displaystyle \sum}}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{N}_{vfd}^{v,t,f,d}$ (11)

$\forall v,f,d:{\nu}_{fd}^{v,f,d}=2\left[{\zeta}_{fd}\left(\frac{\gamma}{{\rho}_{v}}+{\beta}_{v}\right)\right]+{\alpha}_{fd}$ (12)

${\alpha}_{fd}={\epsilon}_{fd}+\{\begin{array}{l}\varphi f{d}_{1},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}1\le {\zeta}_{fd}\le 50\\ \varphi f{d}_{2},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}51\le {\zeta}_{fd}\le 100\\ \varphi f{d}_{3},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}101\le {\zeta}_{fd}\le 150\\ \varphi f{d}_{4},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{\zeta}_{fd}\ge 100\end{array}$ (13)

$\forall v:{T}_{vfd}^{v}=\underset{{f}_{1},{d}_{1},{t}_{1}}{\overset{F,D,T}{{\displaystyle \sum}}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{N}_{vfd}^{v,t,f,d}$ (14)

${\alpha}_{fd},{A}_{prod}^{f,m,p,t},{A}_{tfw}^{f,p,v,w,t},{A}_{twd}^{f,p,v,d,t},{A}_{ware}^{w,p,t},{N}_{vfd}^{v,t,f,d},V{F}^{v},{\nu}_{fd}^{v,t,f,d}\ge 0,\text{integer}$ (15)

$\forall m,f,t:{\sigma}_{act}^{f,m,t}\ge 0,\text{binary}$ (16)

F_{1} is our cost function. The objective is to minimize the total cost Z from Equation (1). Equation (3) ensures that the production line is activated before production. Equation (4) ensures that products moved to the warehouses are equal to the number produced at various factories. Equation (5) ensures that the initial amount of product at the internal warehouse is products produced and stored at t_{0}. Equation (6) updates of the number of products at the warehouses. Equation (7) ensures storage capacity is put in check. Equation (8) ensures that products are transport based on previous storage capacity.

To meet all demand, Equation (9) controls the final transportation of the product at times *t*. Equation (10) ensures that the total transported products do not exceed the total capacity of the vehicle used.

Equation (11) and (14) estimates the number of vehicles used. Equation (12) estimates the vehicle operational cost. Equation (13) computes the driver’s operational cost. All drivers are entailed to a daily fixed cost “ ${\u03f5}_{\ast \ast}$ ” and a series of additional cost “ ${\varphi}_{\ast \ast}$ ” depending on the distance traveled. Lastly Equations (15) and (16) are the non-negative and binary constraints for all the decision variables.

3. Computation, Results and Discussion

The model was computed using the CPLEX solver in AMPL. The expanded model contains one quadratic objective function, 5568 decision variables, and 2928 linear constraints. The model was computed under one minute performing 7030 mixed-integer simplex iterations and 2914 branch-and-bound nodes.

Due to geographical location of the factories, there will be long hauling of products to most distributors. Out of the 16 regions, 11 were served by a single factory, while the remaining five were served by the two factories combined. Again, the Spintex and Ahinsan factories served 59 and 46 distributors respectively, shown in Figure 3.

If every vehicle is to be moved once, then according to Figure 4 we have a total of 146 vehicles (36 of v_{1}, 10 of v_{2}, 27 of v_{3}, 17 of v_{4}, and 56 of v_{5}). Out of the 36

Figure 3. A map showing the distribution routing.

Figure 4. Vehicle distribution to 105 distributors.

of vehicles v_{1} used, 17 and 12 transported to Accra and Kumasi respectively.

In all cases, the total capacity of all combined vehicles used was proportional to the quantity demanded. Due to the largest cargo capacity of v_{1}, it transported to locations with more peak demand except when the demand was more than the vehicle’s capacity. In this situation, other vehicles will be considered if using two of v_{1} will leave more empty spaces on the vehicle. The optimal selection of the vehicle depends on vehicle capacity, performance, maintenance cost, and the miles the vehicle is traveling. The distance to be traveled affects the choice of the vehicle since maintenance cost and driver’s operational cost are computed with respect to the distance. If a vehicle with a higher maintenance cost travels a longer distance, it incurred a higher cost then using a low-maintenance vehicle. Vehicle v_{5}’s were used to haul loads of less than 680 products. The ideal vehicle for this quantity of products should have been a v_{6} which was not used due to its high maintenance cost. Since both factories are equipped to manufacture both products, each vehicle is carefully chosen to optimize vehicle loading. In a sensitivity analysis, if the maintenance cost of vehicle v_{6} is reduced to GHs 3.50, then transportation below 680 will be transported by v_{6} instead of v_{5}.

Elaborating on a specific scenario, Amanfrom needs 2944 combined products. The largest vehicle in the fleet is v_{1} which can haul 2860 products. Choosing v_{1} indicates another vehicle has to be used to convey the remaining 84 products. Now in the transportation fleet, no other vehicle can load the remaining products without leaving more empty spaces. Vehicles v_{3} and v_{4} where used instead. v_{3} possessing a loading capacity of 1800 hauled 1441 of crates of soft beverage and 153 boxes of minute maid while v_{4} with a 1350 carrying capacity hauled the remaining 1350 crates of soft beverage. The choice of vehicles was also influenced by the performance and maintenance cost of each vehicle. Under this scenario, using vehicles v_{2} and v_{5} will only leave an empty space of 36 instead of 206 from using v_{3} and v_{4}.

The result show that 36 of vehicles v_{1} was used to transport products to 8 distributors, 10 of vehicles v_{2} was used to transport products to 7 distributors, 27 of vehicles v_{3} was used to transport products to 22 distributors, 17 of vehicles v_{4} was used to transport products to 17 distributors, 56 of vehicles v_{5} was used to transport products to 56 distributors and none of vehicle v_{6} was used. The solution suggested that; moving a fully-loaded vehicle outweighs the benefit of moving an empty or a partially loaded vehicle. Generally, trucks operating cost does not depend on the quantity of a product in the truck [12]. Again, different types of vehicles can be used to transport products on a single route to a specific distributor. There was no case where vehicle v_{5} was used more than once on a particular route yet recorded the highest number of vehicles. This justifies that, most of the demand falls within the capacity of the vehicle. Therefore, demand remains another factor to consider when deciding on the types of vehicles to include in a transportation fleet. According to Table 1 the number of vehicles increases with a decrease in the vehicle capacity and Figure 5 represents the cost function value of each type of fleet.

Table 1. Objective cost respect to vehicle type.

**Different Capacities.

Figure 5. Vehicle distribution to 105 distributors.

4. Conclusions

Using Mixed-Integer Quadratic Programming (MIQP) model, a Multi-Factory Vehicle-Type Routing Problem (MFVTRP) decides on the type of vehicle used for each required shipment after an optimal routing.

The formulated model and analysis have shown that the existence of multiple vehicles in a fleet purposefully for long hauling goods also renders an optimal minimum cost as compared to a single-vehicle fleet as already indicated by [4] in the public-transport sector.

In the multiple vehicles fleet, 36 of vehicles v_{1}, 10 of vehicles v_{2} 27 of vehicles v_{3} 17 of vehicles v_{4}, 56 of vehicles v_{5} and none of vehicles v_{6} were used to transport Coca-Cola products to the 105 distributors across Ghana. Out of the 16 regions, 11 were served by the Ahinsan factory, while the remaining five were served by the two factories combined. Again, the Spintex and Ahinsan factories served 59 and 46 distributors respectively.

Using the selected vehicles accounted for a transportation cost of 0.2066 of the total cost incurred by the two factories. This justifies a 25% transportation cost-reduction when MIQP was used to supply goods to distributors. Again, a single-vehicle fleet with loading capacity within the mean value of all individual demands gave a minimum cost next to the optimal minimum.

References

[1] Angueiraa, J., Konduria, K., Chakourb, V. and Eluruc, N. (2017) Exploring the Relationship between Vehicle Type Choice and Distance Travelled: A Latent Segmentation Approach. The International Journal of Transportation Research, 11, 146-157.

https://doi.org/10.1080/19427867.2017.1299346

[2] Guedes, P.C. and Bornstein, D. (2015) Column Generation Based Heuristic Framework for the Multiple-Depot Vehicle Type Scheduling Problem. Computers and Industrial Engineering, 90, 361-370.

https://doi.org/10.1016/j.cie.2015.10.004

[3] Guedes, P.C. and Bornstein, D. (2018) Real-Time Multi-Depot Vehicle Type Rescheduling Problem. Transportation Research Part B: Methodological, 180, 217-234.

https://doi.org/10.1016/j.trb.2017.12.012

[4] Ceder, A. (2011) Optimal Multi-Vehicle Type Transit Timetabling and Vehicle Scheduling. Procedia-Social and Behavioural Sciences, 20, 19-30.

https://doi.org/10.1016/j.sbspro.2011.08.005

[5] Manuel, O. and Alexander, H. (2018) Vehicle Selection for a Multi-Compartment Vehicle Routing Problem. European Journal of Operational Research, 269, 682-694.

https://doi.org/10.1016/j.ejor.2018.01.059

[6] Gintner, V., Kliewer, N. and Suhl, L. (2005) Solving Large Multiple-Depot Multiple-Vehicle Type Bus Scheduling Problems in Practice. OR Spectrum, 27, 507-523.

https://doi.org/10.1007/s00291-005-0207-9

[7] Ramesh, G., Sudha, G. and Ganesan, K. (2018) Solution of Two Vehicle Cost Varying Interval Transportation Problem—A New Approach. International Journal of Pure and Applied Mathematics, 119, 363-372.

[8] Cantarella, G.E., Febbraro, A.D. and Gangi, M.D. (2019) Stochastic Multi-Vehicle Assignment to Urban Transportation Networks. 2019 6th International Conference on Models and Technologies for Intelligent Transportation Systems, Cracow, 5-7 June 2019, 1-8.

https://doi.org/10.1109/MTITS.2019.8883351

[9] Sarker, B.R., Faiz, T.I. and Ganesan, K. (2017) Minimizing Transportation and Installation Costs for Turbines in Offshore Wind Farms. Renewable Energy, 101, 667-679.

https://doi.org/10.1016/j.renene.2016.09.014

[10] Cao, X., Mokhtarian, P.L. and Handy, S.L. (2006) Neighbourhood Design and Vehicle Type Choice: Evidence from Northern California. Transportation Research Part D: Transport and Environment, 11, 133-145.

https://doi.org/10.1016/j.trd.2005.10.001

[11] Masson, R., Trentini, A., Lehuédé, F., Malhéne, N., Péton, O. and Tlahig, H. (2015) Optimization of a City Logistics Transportation System with Mixed Passengers and Goods. EURO Journal on Transportation and Logistics, 6, 81-109.

https://doi.org/10.1007/s13676-015-0085-5

[12] Jordan, W.C. and Burns, L.D. (1984) Truck Back-Hauling on Two Terminal Networks. Transportation Research Part B: Methodological, 18, 487-503.

https://doi.org/10.1016/0191-2615(85)90014-1