EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 14, No. 4, 2021, 1112-1131 ISSN 1307-5543 – ejpam.com Published by New York Business Global Developing Just-In-Time and Network Flow Models For Urban Snow Removal Problem Zeinab Bandpey1,∗, Ahlam Tannouri2, Isabelle Kemajou-Brown2, Asamoah Nkwanta2 1 Division of Mathematics, Science, Technologies and Business, Northern Virginia Community College, Woodbridge, VA, USA 2 Department of Mathematics, Morgan State University, Baltimore, MD, USA Abstract. Winter urban traffic issues and performance present critical problems in large cities and metropolitan areas. In urban areas, there is a critical need for efficient methods for snow removal while considering the impact on the transportation infrastructure of a city. Several proposals and approaches on modeling snow removal that heuristically deals with finding solutions to this wide- open problem have been studied and published in recent years. In this paper, we developed a new mathematical model that uses the Just-In-Time (JIT) method to optimize a transportation problem. The paper’s main objective is to design a model for establishing efficient truck routes for snow removal by optimizing cost and time, which implicitly minimizes the impact on a city’s transportation infrastructure. We applied the network flow problem for snow removal to minimize time and cost of cleaning urban streets just in time. We ran several simulations of the models using the MATLAB®. 2020 Mathematics Subject Classifications: 90B06, 90B35, 90C05, 05c21,68Q05 Key Words and Phrases: Just InTime, Urban Snow Removal, MATLAB®, Network flow, Multi-objective optimization 1. Introduction The Just-In-Time (JIT) inventory system is known as an asset management tool. It gives companies an inventory strategy that may be used to increase efficiency and decrease waste by receiving goods only as needed in the production process. This model requires that all demanded goods be transported to their destinations on schedule at zero or minimum destination storage and transportation cost [7]. The Bai-Gan JIT model was extended to tackle transportation problems in 2011 [6]. ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v14i4.4082 Email addresses: zbandpey@nvcc.edu (Z. Bandpey), Ahlam.Tannouri@morgan.edu (A. Tannouri), Elisabeth.Brown@morgan.edu (E. Brown), Asamoah.nkwanta@morgan.edu (A. Nkwanta) http://www.ejpam.com 1112 © 2021 EJPAM All rights reserved. Z. Bandpey et al. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1112-1131 1113 This paper develops a new mathematical model based on the Bai-Gan Just-In-Time method to optimize the snow removal transportation problem. The model is designed to establish efficient truck routes by optimizing budget and time. The network flow prob- lem, introduced in [10], is applied for snow removal to minimize the street clearing cost just in time. We ran several simulations of the proposed models to obtain the optimal solutions using MATLAB®. The outcome of the models introduced in our paper provides alternative plans of action to be used by urban city planners for better performance. The introduced models can be applied to rural areas with constraints modifications that satisfy the nature of snow removal in these areas. Cities with heavy snowfall in the United States have long suffered from large financial losses due to closing businesses during a heavy snowstorm. On May 4, 2015, the American Association of the States Highway and Transportation Officials said 23 states reported combined spending of more than one billion dollars on winter maintenance operations and eight million work hours plowing and treating state roads from October 2014, to March 2015 [8]. An important key outcome for winter traffic maintenance is the effectiveness and efficiency of snow removal from public roadways since everyday life activities of the popu- lation in snowy winter cities depends on it ([2], [4], [5]). A vast body of literature exists on transportation asset management; several research papers that develop asset management systems for snow removal have been published, such as [5] and references therein. These research papers developed systems that provide efficient snow plowing routes and optimize snow removal resources and assets allocations [3], but there seems to be little literature on using JIT model to tackle this problem. The research implemented in [2] covers how route assignments can improve the efficiency of snow removal problem. It deals with the problem of designing efficient routes for salting and plowing trucks during snow emergencies. The problem is formulated as a mathemati- cal optimization problem and is classified as a capacitated rural postman problem, which is an arc routing problem. Several heuristic algorithms and their combinations are proposed to solve the real-world vehicle routing problems for snow emergencies in Calvert County in Maryland. The researchers in [3] developed an intelligent asset management system for snow removal in collaboration with Black Hawk County, IA, the city of Columbia, MO, and the Iowa Department of Transportation. They used Geographic Information Systems (GIS) and Artificial Intelligence (AI) techniques to implement a web-based Winter Maintenance De- cision Support System (WMDSS). WMDSS uses the Hungarian Algorithm and heuristic based algorithms to evaluate different procedures for managing snow removal assets op- timally; it provides expert advice to assist in complex decision making, such as routing, optimal resource allocation, and monitoring live weather information. Maryland Department of Transportation State Highway Administration Z. Bandpey et al. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1112-1131 1114 (SHA) Rules and Regulations • According to SHA policy [9], SHA and Contract Forces are jointly responsible for minimizing the impact on our environment and min- imizing winter operation costs. • Winter operations strategies consist of the following: (a) Anti-Icing: is a proactive winter strategy of preventing snow or ice from bonding to the pavement. It involves a timely application of pre-watered salt or liquid chemicals on highways, usually before the start of a storm. (b) Deicing: is a traditional reactive winter maintenance strategy of breaking the snow/ice and pavement bond once formed. It requires large amounts of salt to work through the snowpack and break its bond to the pavement. It results in higher safety costs due to delays in achieving bare pavement. Deicing also leads to more damages to the environment and highway system. (c) Plowing: is an active winter strategy for clearing away snow from highways, railroad tracks, etc.. • There are four different call-out phases: (1) (0-1 inch forecast or < 0.1 inches of freezing precipitation) includes only SHA Trucks. (2) (1-2 inch forecast or 0.1 − 0.2 inches of freezing precipitation) includes Phase 1 trucks and hired spreader trucks to supplement SHA workforces on designated routes with no assigned SHA Trucks. (3) ( 2-4 inch forecast or > 0.2 inches of freezing precipitation) includes Phase 2 trucks and hired spreader trucks to supplement the SHA workforces during heavier snowfalls. (4) ( > 4−inch forecast or significant freezing precipitation) includes all phase 3 trucks and hired push trucks to supplement SHA workforces on designated routes as roadway condition warrant. • Roadways and surfaces: (1) Two-lane roadways: is one 12 foot wide lane traveling in each direction. The standard plow angled correctly will clear 8 to 9 feet per pass. Four passes are needed to clear the entire road. (2) Multi-lane Highways: is multi-lanes traveling in both directions. Road width de- termines the number of plow trucks needed. • Types of Plows: (1) One way reversible plow ( manual adjust) (2) One way reversible plow (hydraulic adjust) (3) One way non-reversible plow (4) wing plow (5) V- plow: it plows in both direction at the same time. • Plowing options: (1) Two-way road single Truck: it plows lane in one direction and drops salt behind the truck. After plowing in one direction, it turns at the end of the route, plows the lane in the opposite direction, and drops salt on both lanes. Z. Bandpey et al. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1112-1131 1115 (2) Two-way road two trucks: (3) Multi-vehicle plowing: First truck clears 8 feet of the left traffic lane, leaving 4 feet for the second truck. Second truck overlaps one foot clearing 4 feet of the first lane and 3 feet of the second lane, leaving 9 feet for the third truck. Third truck overlaps 1 foot clearing 7 feet of the second lane, leaving 2 feet for fourth truck. Fourth truck overlaps 1 foot clearing 2 feet of the second lane 5 feet of shoulder. One more truck would be required if the third lane was present. 2. Preliminaries 2.1. Bai-Gan JIT Transportation Model In this section JIT is referred to as Bai-Gan JIT, which describes both a mathematical model and an algorithm published in 2011 [6]. Let m, k, n ∈ N , where N is the set of natural numbers, be given. Let A1, A2, ..., Am be resources or manufactures, G1, G2, ..., Gk be commodities, and ail be the production of Gl produced by Ai, 1 ≤ i ≤ m, 1 ≤ l ≤ k. Let B1, B2, ..., Bn be marketing destinations that demand those commodities and let bjl Z. Bandpey et al. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1112-1131 1116 be the amount of Gl requested by the destination Bj , 1 ≤ j ≤ n, 1 ≤ l ≤ k. Suppose that tij is the time needed for shipping goods from Ai to Bj and cijl is the corresponding unit transportation cost for the commodity Gl. Suppose tj is the demanding time for all requested commodities to be shipped to Bj . Let xijl be the quantity of the commodity Gl shipping from Ai to Bj . The philosophy of JIT is represented by the conditions: (tij − tj)xijl = 0, 1 ≤ i ≤ m, 1 ≤ j ≤ n, 1 ≤ l ≤ k. (1) Then, the JIT-transportation problem is defined as the following multi-objective program- ming problem: min z = m∑ i=1 n∑ j=1 k∑ l=1 cijlxijl, s.t. (tij − tj)xijl = 0, 1 ≤ i ≤ m, 1 ≤ j ≤ n, 1 ≤ l ≤ k. n∑ j=1 xijl ≤ ail, (i = 1, 2, ..., m), (l = 1, 2, ..., k) m∑ i=1 xijl = bjl, (j = 1, 2, ..., n), (l = 1, 2, ..., k) xijl ≥ 0, (1 ≤ i ≤ m, 1 ≤ j ≤ n, 1 ≤ l ≤ k) The time deviation and functions were introduced as follows; Let dij = max{tij − tj , 0}, define F (x) = max{dij : xijl = 0, 1 ≤ i ≤ m, 1 ≤ j ≤ n, 1 ≤ l ≤ k}, (2) and f(x) = k∑ l=1 m∑ i=1 n∑ j=1 cijlxijl, (3) where x = (xijl) ∈ R(mnk). Then the JIT-transportation problem can be expressed as min z = ω1p1 + ω2p2 (4) such that F (x) + n1 − p1 = 0 f(x) + n2 − p2 = 0 n∑ j=1 xijl = ail, 1 ≤ i ≤ m, 1 ≤ l ≤ k Z. Bandpey et al. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1112-1131 1117 m∑ i=1 xijl = bil, 1 ≤ j ≤ n, 1 ≤ l ≤ k xijl ≥ 0, 1 ≤ i ≤ m, 1 ≤ j ≤ n, 1 ≤ l ≤ k ns ≥ 0, ps ≥ 0, s = 1, 2, negative resp. positive deviational variable with nkpk = 0, k = 1, 2, ωk : given priority factor A. Definitions (a) Let x ∈ D be given, where D is the set of feasible solutions (4). If F (x) = 0, then x is called a JIT solution to (4); if F (x) ̸= 0, then x is called a deviation solution of this JIT-transportation problem. (b) Let m, n, k ∈ N be given. Let dij = max{tij − tj , 0}, 1 ≤ i ≤ m, 1 ≤ j ≤ n. For λ ≥ 0, we define B(λ) = {(i, j, l)|dij ≤ λ, 1 ≤ i ≤ m, 1 ≤ j ≤ n, 1 ≤ l ≤ k}. (c) The B(λ)− transportation problem of the JIT-transportation problem (4) is min g(λ, x) = ∑ (i, j, l)∈B(λ) cijlxijl +M ∑ (i, j, l)/∈B(λ) xijl s.t. x ∈ D where M is a sufficiently large positive number. B. Emergency Transportation Problem When a catastrophic event such as an earthquake or a snowstorm has already oc- curred, the primary consideration of the emergency management officials is to assign or to ship certain critical supplies, equipment, or personnel to specific locations as soon as possible. Another consideration is to minimize the transportation cost. We call such a transportation problem the emergency transportation problem. The transportation problem for emergency management is usually treated as multi- objective programming or goal programming problem. Z. Bandpey et al. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1112-1131 1118 C. Goal Programming min fk = m∑ i=1 n∑ j=1 ckijxij , (k = 1, 2, ..., w) s.t. n∑ j=1 xij = ai, (i = 1, 2, ..., m) m∑ i=1 xijl = bj , (j = 1, 2, ..., n) xij ≥ 0, (1 ≤ i ≤ m, 1 ≤ j ≤ n) where fk is the kth objective function which represents one of the considerations mentioned above, ckij is the cost of transporting certain commodity from the ith origin to the jth destination under the consideration of the kth target function, and xij is the quantity of certain commodity being shipped from the ith origin to the jth destination. 2.2. Graph-Theoretic Modeling 2.2.1. Network Flow Problem In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and receives a flow. The amount of flow cannot exceed the edge’s capacity. Often in operations research a directed graph is called a network, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction; that is the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or a sink, which has only incoming flow. A network can be used to model traffic in a computer network, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes [21]. Let. A network is a graph G = (V,E), where V is a set of vertices and E is a set of V ′s edges - a subset of V × V - together with a non-negative function c: V × V → R∞, called the capacity function. Without loss of generality, we may assume that if (u, v) ∈ E, then (v, u) is also a member of E, since if (v, u) ̸∈ E, then we may add (v, u) to E and then set c(v, u) = 0. If two nodes in G are distinguished, the node source s and the node sink t, then (G, c, s, t) is called a flow network[21]. A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V , such that every edge connects a vertex in U to one in V . Vertex sets U and V are usually called the parts of the graph[21]. Z. Bandpey et al. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1112-1131 1119 Minimum cost maximum flow For a network G = (V,E), the cost of a flow f is defined as: c(f) = ∑ e∈E f(e).c(e) A minimum cost maximum flow of a network G = (V, E) is a maximum flow with the smallest possible cost[21]. 3. Developing the JIT Snow Removal Model Since the snow removal is a multi-objective optimization problem, we will formulate a mathematical model based on multi-objective linear programming or goal programming to minimize the objective variables. The process is as follow: (i) Identify the decision variables in the problem. (ii) Identify and formulate the objectives and constraints. (iii) Solve the problem for each of the objectives identified in step (ii) to determine the optimal value of each objective. (iv) Restate the objectives as goals using the optimal objective values identified in step (iii) as the target values. (v) Define a deviational variable for the difference between service time and the due time. It could be either positive (measuring how much a given solution fails to meet the due time goal) or negative (measuring how much it overachieves the goal). (vi) For the variable identified in step (v), assign a weight to the function and create a constraint that requires the value of the weighted deviational variable to be less than a defined Max point (defined in section 3.3). (vii) Find a solution that satisfies the constraints and comes closest to meeting the goals. (viii) Inspect the solution to the problem. If the solution cannot be implemented on the ground or is not approved by authorities, adjust the weights in step (vi) and return to step (vii). The Snow Removal model has five main components to be considered: • Transporting single commodity or more (for example: snow, sand). • Having multi-origin and multi-destination. • Minimizing the transportation cost. Z. Bandpey et al. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1112-1131 1120 • Minimizing the time deviation. • Several moving methods. We divide the snow removal model into three sub-models based on the development of snow: (a) The first stage is spreading sands and salt brine on the streets before the start of the snowfall (Anti-Icing). (b) The second stage is spreading sands and salt brine on the streets after the snow (De-icing). (c) The third stage is snow plowing. (d) The fourth stage (possible in case of a heavy snowstorm) is to use trucks to move heavy snow to some designated locations that we call dumping stations. Mathematical models for those four cases could be similar, and we will explain one of the cases in the following section. 3.1. Formulation of the Bai-Gan JIT Model as a JIT Snow Removal Model Suppose that there arem truck departuresA1, A2, ..., Am that provide k typesW1, W2, , ...,Wk of trucks capacities. Let ail be the number of trucks with capacity Wl, 1 ≤ l ≤ k departed from Ai, 1 ≤ i ≤ m . We will assume that all trucks are multi-tasks. When a specific task is not in use, we assign 0 to its corresponding defined parameter. Suppose there are n snow depots (a depot can be defined as a side of a street or a specific destination) B1, B2, ..., Bn to where the trucks dump the snow. The number of trucks of capacity Wl needed to transport snow at destination Bj is bjl, and the due time for all trucks transporting snow to Bj is tj ; the due time tj would be determined depending on the snow density and volume. Suppose that the time for salting, plowing the snow on the side road, or hauling it to the specific destination using the truck with capacity Wl from Ai to Bj is tij , and the unit cost for such service is cijl. Finally, let xijl denote the number of trucks of capacity Wl traveling from Ai to Bj . The conditions for the JIT model can also be represented by (tij − tj)xijl = 0, 1 ≤ i ≤ m, 1 ≤ j ≤ n, 1 ≤ l ≤ k. (5) If xijl is greater than 0, at least one truck travels from Ai to Bj . For equation (5) to hold, we need tij = tj , which means the due time equals to service time. We define the Snow removal JIT-Transportation problem as the following programming problem: minz = m∑ i=1 n∑ j=1 k∑ l=1 cijlxijl Z. Bandpey et al. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1112-1131 1121 s.t. (tij − tj)xijl = 0 1 ≤ i ≤ m, 1 ≤ j ≤ n, 1 ≤ l ≤ k. n∑ j=1 xijl ≤ ail, 1 ≤ i ≤ m, 1 ≤ l ≤ k. m∑ i=1 xijl = bjl 1 ≤ j ≤ n, 1 ≤ l ≤ k. Illustrative Example 1. Suppose that A1, A2, A3 are three truck departures such that each of them provides three types of trucks with different capacities G1, G2, G3. The distribution of trucks is listed in table 1. There are four snow depots; namely B1, B2, B3, B4, which have limited capacities of snow holding shown in table 2. Tables 3 and 4, show the demand due times (DT) and costs between truck departure locations and snow depots. Table 1: Supplies. Types of Truck Capacity Trucks Departures G1 G2 G3 A1 0 26 25 A2 58 10 35 A3 42 24 18 Table 2: Snow Depot Limits. Types of Truck Capacity Snow Depot G1 G2 G3 DT B1 25 0 0 5 B2 30 26 47 7 B3 20 20 10 9 B4 10 14 32 6 Table 3: Shiping Time. Snow Depots Truck Departures B1 B2 B3 B4 A1 10 9 8 5 A2 5 10 9 8 A3 4 7 13 6 Z. Bandpey et al. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1112-1131 1122 Table 4: Unit Transportation cost. Snow Depots Truck Departures B1 B2 B3 B4 A1 8 12 14 17 A2 9 7 11 12 A3 13 14 9 17 The problem as formulated above does not have a feasible solution verified as well using MATLAB, see the page url: https://github.com/bandpey65/JIT-Snow_removal_Ex1/ blob/405a89990c7cd3e27f9551a1f39d249ffac8cb78/JITSnowremovalEx1.m We propose different approaches to solve the problem. 3.2. The Penalty-Allocation Method: Let dij = max{tij − tj , 0}, we define F (x) = max{dij : xijl = 0, 1 ≤ i ≤ m, 1 ≤ j ≤ n, 1 ≤ l ≤ k}, (6) and f(x) = k∑ l=1 m∑ i=1 n∑ j=1 cijlxijl, (7) where x = (xijl) ∈ Rmnk. Then the JIT-transportation problem can be expressed as min z = ω1p1 + ω2p2 (8) such that F (x) + n1 − p1 = 0 f(x) + n2 − p2 = 0 Case1 : dij = 0 then tij − tj ≤ 0 which means the truck arrive from Ai to Bj before or on due time, Also F (x) = 0, since F (x) + n1 − p1 = 0 hence n1 = p1 = 0; Case2 : dij ̸= 0 then tij − tj > 0 which means the truck arrive from Ai to Bj after due time, Also F (x) > 0, since F (x) = p1 − n1 hence p1 > n1, and n1 = 0. Remark 1. Note that tij − tj < 0 implies that the truck arrives before due time; also, (5) imposes xijl = 0, which means no truck is assigned to travel from Ai to Bj. Z. Bandpey et al. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1112-1131 1123 Remark 2. By defining priority factors, we could prioritize time over cost or vice versa. s.t. n∑ j=1 xijl = ail, m∑ i=1 xijl = bjl, xijl ≥ 0, 1 ≤ i ≤ m, 1 ≤ j ≤ n, 1 ≤ l ≤ k ns ≥ 0, ps ≥ 0, s = 1, 2, negative resp. positive deviational variable with nkpk = 0, k = 1, 2, ωk : given priority factor. Illustrative Example 2. We We ran a simulation to solve the same example using the above formulation. We randomly assigned W1 to be 3 and W2 to be 1. The proposed approach and the changes we made did not lead us to find a feasible solution. See the page url: https://github.com/bandpey65/JIT-Snow_removal_Ex2/blob/ a157461980155601e304809e56566b3fa5baee51/JIT-Snow_removal_Ex2.m Note: These numbers can be changed to prioritize the variables in different ways to satisfy the goals of the organization in charge such as SHA. 3.3. Balanced Transportation Problem: Definition: (i) Let x ∈ D be given, where D is the set of feasible solutions. If F (x) = 0, then x is called a JIT solution of (4); if F (x) ̸= 0, then x is called a deviation solution of this JIT-transportation problem. (ii) Let m, n, k ∈ N, be given. Let dij = max{(tij − tj), 0}, 1 ≤ i ≤ m, 1 ≤ j ≤ n. For λ ≥ 0, we define B(λ) = {(i, j, l)|dij ≤ λ, 1 ≤ i ≤ m, 1 ≤ j ≤ n, 1 ≤ l ≤ k}. Z. Bandpey et al. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1112-1131 1124 (iii) The B(λ)-JIT-transportation problem (4) is min g(λ, x) = ∑ (i, j, l)∈B(λ) cijlxijl +M ∑ (i, j, l)/∈B(λ) xijl s.t. x ∈ D where M is a sufficiently large positive number. s.t. n∑ j=1 xijl = ail, m∑ i=1 xijl = bjl, xij ≥ 0, where 1 ≤ i ≤ m, 1 ≤ j ≤ n, 1 ≤ l ≤ k, and all cijl, tij , tj , ail, bil are nonnegative. Illustrative Example 3. In this example, we modified the formulation of the problem and the constraints; we obtained an optimal solution. Optimal solution found. x111 = 20, x131 = 30, x151 = 20, x221 = 30, x251 = 20, x331 = 10, x341 = 60, x112 = 50, x132 = 30, x152 = 10, x222 = 40, x252 = 50, x332 = 20, x342 = 70, and xijl = 0 for all other xijl. See the page url: https://github.com/bandpey65/JIT-Snow_removal_Ex3/blob/ 1adf2c2cdaafcd585bb6f15488859cdb9286f967/JIT-Snow_removal_Ex3.m 4. An Application of a Network Flow Algorithm to Solve a Snow Removal Problem This section begins by representing the snow removal problem as a network flow described in section 2.2.1 We consider the streets map as a directed graph G = (V,E). The set of vertices V represents locations, and the set of edges E represents streets connecting them; we are using a directed graph so that the directions of streets would be taken into consideration. The departure points for trucks are the salt storages defined as source nodes, and the destinations (places/place to dump the snow) are defined as sink nodes. The Ai, i = 1, ...n are the nodes representing the start points of the routes which are assigned a number of available resource loads at that node; for instance, in the case of Z. Bandpey et al. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1112-1131 1125 de-icing, the available resource could be the amount of salts loaded in the trucks. The Bj , j = 1, ...m are the end nodes representing the end point of the routes and assigned a number which is the demand load. Each edge in the network representing a street has a non-negative capacity c(e); the capacity can be defined as a multi-variable function since many factors are involved such as truck’s salt capacity and gas consumption, width of street and density of snow. In our study we define the capacity only in function of time and cost not taking into consideration width of the streets and density of the snow. The same process can be applied for each classification of the roads and amount of snow following SHA’s designation of snow phases and roadways type as explained in 2.1. Time or cost can be prioritized or simply combined. We define a capacity function based on the actual unit cost and lateness penalty cost; if the work is done after the due time, a lateness penalty would be added to the actual cost. The capacity function is defined by c(eij) = Cij +αT (i, j), where α is the lateness penalty coefficient. Different values can be assigned to α depending on whether we are treating urban or rural roads, and as defined in 3.1, T (i, j), the deviation of time is given by t(i, j)−DT . The goal is to minimize the total cost Cij , which correlates directly to minimizing the penalty α incurred due to time deviation. Illustrative Example 4. Let us consider a modified version of Example 3, where each element in every row for the supply and demand table represents the sum of entries of the corresponding row in example 3. Table 5: Supplies. Trucks Departures Supplies A1 51 A2 103 A3 84 Table 6: Demands. Snow Depots Demands B1 25 B2 104 B3 50 B4 56 The entries in the time deviation table below are calculated by T (i, j) = t(i, j)−DT , using the service time and due time values from example 3. The entries in the unit transportation cost table below are calculated by c(eij) = Cij + αT (i, j), using the cost values from example 3. Z. Bandpey et al. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1112-1131 1126 Table 7: Time Deviation. Snow Depots Truck Departures B1 B2 B3 B4 A1 5 2 −1 −1 A2 0 3 0 2 A3 −1 0 4 0 Table 8: Unit Transportation cost after applying lateness penalty. Snow Depots Truck Departures B1 B2 B3 B4 A1 8 + 5α 12 + 2α 14 + α 17− α A2 9 7 + 3α 11 12 + 2α A3 13− α 14 9 + 4α 17 Note: The entries of this chart represent the cost of moving from node Ai to node Bj . For instance, C(1,1) is equal to 8 + 5α, where the number 5, coefficient of α represents the time deviation. A positive coefficient shows the work has been done after the due time; in this case, five times the penalty α was added to the cost. A negative time deviation shows the work has been done before the due time; for instance, in C(1,4), time deviation is −1, means the work has been done before the due time by one-time unit, so we subtract one time the penalty α from the cost. A bipartite graph designed for network flow would be a better way to represent the case discussed above. It is originated at a node S and terminated at a node T. We assign a large number M to the capacity of each edge coming from S to Ai and from Bj to T . The graph below illustrates how a bipartite graph was used to represent the discussed example. Note that if we have more than one source (Sn) and sink (Tt), n, t ∈ N∗, we would partition our map into smaller parts with one Sn and Tt, to apply the same process to each partition. To find an optimal solution, we solve the problem, considering each partition separately. Several methods can be used to partition the map of a city to find an optimal solution, which will be subject of future research. Z. Bandpey et al. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1112-1131 1127 To ensure the existence of a solution for this problem, we add the nodes A4 and B5 to make the graph above balanced. The model should satisfy the following constraints’ limitations. s.t. n∑ j=1 xijl = ail, m∑ i=1 xijl = bjl, n∑ i=1 ail = n∑ j=1 bjl where 1 ≤ i ≤ m, 1 ≤ j ≤ n, 1 ≤ l ≤ k, and all cijl, tij , tj , ail, bil are nonnegative and as described in 2.2. We formulate the problem as a min-cost flow problem; then, we use linear programming method to solve it. The formulation is as follow: Min CX s.t. Z. Bandpey et al. / Eur. J. Pure Appl. Math, 14 (4) (2021), 1112-1131 1128 AX=b X ≥ 0 Where C = (cij)1×n, A = (aij)m×n, b = (bi)m×1, X = (xij)n×1 We will solve the problem for α = 0, (meaning all the work has been done Just In Time), and similarly, it could be solved for any other value of α. The balanced graph is constructed by adding A4 and B5 as follow: The problem now is formulated as linear programming that can be solved with well- known methods. The MATLAB code can be found at the following url. url:https://github.com/bandpey65/JIT-Snow_removal_Ex4/blob/19803a3fa731e912ed84ab5948c0e8522c566e55/ JIT-Snow_removal_Ex4.m x11 = 0 x12 = 0 x13 = 23 x14 = 30 x15 = 0 x21 = 0 x22 = 0 x23 = 0 x24 = 0 x25 = 103 x31 = 0 x32 = 77 x33 = 7 x34 = 0 x35 = 0 x41 = 23 x42 = 27 x43 = 0 x44 = 0 x45 = 2 5. Conclusion In this paper, we formulate two mathematical models for the snow removal problem. The Bai-Gan JIT algorithm is applied to develop the JIT-Snow Removal Model which minimizes operational cost and time deviation. Recall, time deviation is defined as the difference between service and due times. The priority factors are assigned to the variables time and cost in JIT-Snow Removal Model to enhance the capacity of stakeholders (SHA, transportation personnel, and policy makers). The network flow problem is applied for REFERENCES 1129 snow removal; the cost function is formulated as a multi-objective function that considers both cost and time deviation. This function minimizes the total cost, which correlates directly to minimizing the penalty α incurred due to time deviation. Several examples are illustrated, and solutions are obtained by running simulations of the models using the MATLAB®. The codes are available in an open-source website, and their links are cited in the paper. For future projects, we plan to implement our study to find tangible optimal solutions for the snow removal problem for a specific city. We will use maps of that city to highlight critical places like hospitals, schools, and other localities prioritized by stakeholders. In the model, these localities are represented as key nodes and their connecting streets form the base structure. To perform our task efficiently, we need to gather data about physical locations, characteristics, usage, work history, work planned, costs, resources, and any other information considered relevant by the stakeholder of that city. To validate the efficiency of the proposed models, we may also need information provided by the asset management systems that shows previous years financial reports, the current economic value and future asset value estimates. The successful implementation of this research can provide an optimal and executable solution to the wide-open Snow Removal Problem. Acknowledgements We would like to thank Dr. Xiao-Xiong Gan for his valuable input regarding the Just In Time method and for his time and effort regarding proofreading this research. We would also like to thank Dr. Sam Tannouri, Dr. Jigish Zaveri, and Dr. Young-Jae lee for their support in the early stages of this research. References [1] B. L. Golden and R. T. Wong, Capacited Arc Routing Problems, Networks, pp. 305- 315, 1981. [2] A. Haghani, University of Maryland, Calvert County Snow Emergency Decision Sup- port, Final report to The State Highway Administration, Maryland Department of Transportation, 2000. [3] M.D. Salim, M.A. Timmerman, T. Strauss and M.E. Emch, University of Northern Iowa, Artificial Intelligence-Based Optimization of the Management of Snow Removal Assets and Resources, Report to the Midwest Transportation Consortium, 2002. [4] A. Haghani and M. Hamedi, University of Maryland, Calvert County Snow Emergency Decision Support System, Phase II, Report to The State Highway Administration, Maryland Department of Transportation, 2002. [5] K. Holmberg, Urban Snow Removal: Modeling and Relaxations, Linköpings Univer- sity, LiTH-MAT-R-2014/08-SE. REFERENCES 1130 [6] G. Bai and X. Gan, The JIT Transportation Problem and Its Algorithm, International Journal of Systems Science, Vol 42, No. 12, 2011, 2103-2111. . [7] G. Bai and X. Gan, JIT-Transportation Model and Emergency Management-Rescue Mission, International Journal of Evolution Equations, Vol. 9, No. 1, 2014, 41 - 52 [8] The Associated Press, CBS Baltimore, http://baltimore.cbslocal.com/2015/05/ 04/survey-states-spent-heavily-to-clear-winter-snow-and-ice/, 2015. [9] Maryland Department of Transportation State Highway Administration, https: //www.roads.maryland.gov/OOM/Winter_Hired_Equipment_Presentation_2020_ 2021_FINAL_with_notes.pdf, 2020. [10] F. Armandillo, Job Management and Network Flows, BMI paper, Vrije Universiteit, Faculty of Sciences Business Mathematics and Informatics De Boelelaan 1081,1081 HV Amsterdam, September 2006. [11] E. P. Durbin and D. M. Kroenke, The Out-of-kilter Algorithm: A primer, United States Air Force Project Band, Dec 1968. [12] B. Blandford, E. Lammers, E. Green, Snow and Ice Removal Route Optimization in Kentucky, Transportation Research Record, v 2672, n 45, p 294-304. (2018). [13] A. H. Gundersen, M. Johansen, B. S. Kjoer, H. Andersson, M. Stalhane, Arc Rout- ing with Precedence Constraints: An Application to Snow Plowing Operations, 8th International Conference on Computational Logistics (ICCL 2017), Lecture Notes in Computer Science, , vol. 10572, 174-188. (2017). [14] N. Perrier, A. Langevin, J. F. Campbell, A Survey of Models and Algorithms for Win- ter Road Maintenance. Part III: Vehicle Routing and Depot Location for Spreading, Computers and Operations Research 34, pages 211-257, 2007. [15] N. Perrier, A. Langevin, A. Amaya, Vehicle Routing for Urban Snow Plowing Oper- ations, Transportation Science 42, pages 44-56, 2008. [16] N. Perrier, A. Langevin, J. F. Campbell, The Sector Design and Assignment Problem for Snow Disposal Operations, European Journal of Operational Research 189, pages 508-525, 2008. [17] O. Quirion-Blais, A. Langevin, M. Trepanier, A Case Study of Combined Winter Road Snow Plowing and Deicer Spreading,Canadian Journal of Civil Engineering, v 44, n 12, p 1005-1013.(2017) [18] W. J. Tang, G. Zhang, M. J. Liao, A Framework of Winter Road Maintenance Op- timization, Proceedings - International Conference on Natural Computation, v 2016- January, p 1057-1061, January 8, 2016, 2015 11th International Conference on Natural Computation, ICNC 2015. REFERENCES 1131 [19] J. Wang, H. Liu, Snow Removal Resource Location and Allocation Optimization for Urban Road Network Recovery: A Resilience Perspective, Journal of Ambient Intelli- gence and Humanized Computing, v 10, n 1, p 395-408.(2019) [20] W. Zhou, B. Wu, Model for Snow-fighting Vehicle Route Planning Considering Dead- heading Restriction, ACM International Conference Proceeding Series, October 22, 2018, Proceedings of 2nd International Conference on Computer Science and Appli- cation Engineering, CSAE 2018. [21] P. Zhang, G. Chartrand. 2012. A First Couse in Graph Theory. Mineola, N.Y.: Dover Publications. https://search.ebscohost.com/login.aspx?direct=true& scope=site&db=nlebk&db=nlabk&AN=1151166.