arXiv:1511.06236v1 [cs.RO] 19 Nov 2015 A mass-flow MILP formulation for energy-efficient supplying in assembly lines ∗ Maria Muguerza1, Cyril Briand †1, Nicolas Jozefowiez‡1, Sandra Ulrich Ngueveu§1, Victoria Rodríguez¶2 and Matias Urenda Moris∥3 1CNRS, LAAS, UPS, INSA, INP, 7 avenue du colonel Roche, F-31400 Toulouse, France 2Economics and Management School, University of Navarra„ 31080 Pamplona, Spain 3Virtual Systems Research Centre, University of Skövde, PO Box 408, 54128 Skövde, Sweden September 3, 2018 Abstract This paper focuses on the problem of supplying the workstations of assembly lines with components during the production process. For that specific problem, this paper presents a Mixed Integer Linear Program (MILP) that aims at minimizing the energy consumption of the supply- ing strategy. More specifically, in contrast of the usual formulations that only consider component flows, this MILP handles the mass flow that are routed from one workstation to the other. Keywords: Supplying strategy Assembly lines Energy efficiency MILP. 1 Introduction In general, feeding systems of assembly lines are composed by a central ware- house, several workstations organized in sequence and a fleet of vehicles (tow ∗This work was supported by the ECO-INNOVERA-1rst call EASY (ANR-12-INOV-0002). †briand@laas.fr ‡njozefow@laas.fr §ngueveu@laas.fr ¶vrodriguez@unav.es ∥matias.urenda.moris@his.se 1 trains) in charge of delivering the components to the workstations. The compo- nents are packed in pallet or boxes. The supermarket is a decentralized area of material supplies, located next to the assembly line. For building up a supply- ing strategy, time is discretized in a set of delivering periods. For each period, a workstation has a component consumption (possibly periodic) expressed in terms of boxes. At each tour, the tow trains load the boxes which have to be shipped to the assembly line, follow a supplying route, and stop at the appropri- ate workstations for delivering its boxes. The supplying routes are usually fixed and start and finish at the supermarket. The number of boxes that a tow train can transport in the same tour is limited. The number of boxes available at each workstation should never exceed the storage capacity of the workstation (which is usually low). A supplying strategy defines whether a vehicle has to stop at each workstation at each time period and the number of boxes that should be delivered. In a world where natural resources are limited, issues related to energy ef- ficiency are becoming more and more important. Vehicles in factories travel a significant quantity of kilometers for supplying the workstations, causing effects in economic and energetic expenses. Whether they use electric energy or fossil fuel, their energetic consumption is not negligible and more and more attention has to be paid for exhibiting energy-efficient supplying strategies. Several fac- tors that are inherent to the problem have impact on the energy consumption. We are interested in determining the most significant ones. In the literature related to the Vehicle Routing Problem (VRP), some re- searchers take interest in minimizing carbon dioxide emissions. One of the major contribution is due to Bektas and Laporte [2] who present the Pollution-Routing Problem (PRP) as an extension of the VRP with Time Windows. The PRP consists of routing a number of vehicles to serve a set of customers within pre- set time windows, and determining their speed on each route segment, so as to minimize a function comprising emissions and driver costs. The author propose a MILP formulation that allows to optimize both load and speed of the vehi- cles.The idea of controlling the vehicle velocity on each route segment is fruitful for improving the energy efficiency in the context of long distance transporta- tion problem. However, in a very local transportation context, as the distances travelled during the acceleration phase becomes non-negligible with respect to the one covered at the maximum speed, other parameters can impact the energy consumption. The problem considered in this paper can be viewed as a particular Inven- tory Routing Problem (IRP) . We intend to show that minimizing the travelled distance does not necessarily implies the minimization of the energy. We prove that other parameters can significantly influence the energy spending. The re- mainder of this paper is organized as follows. An energy consumption analysis is proposed in Section 2. A MILP for energy optimization is described in Section 3. 2 2 Energy modeling The forces that have more influence on the power consumed by the vehicle are: the traction force (Ft = mT a(t)) and the rolling resistance (FrmT = gCr), in Newtons (N). The traction force is used to generate motion between an object and a tangential surface, and it depends on the mass (mT ) and the acceleration of the vehicle (a(t)). The rolling resistance is the force resisting the motion when a body rolls on a surface and varies in function of the load (mT ), the rolling coefficient (Cr) and the gravity (g). The parameter (mT ) represents the mass of the vehicle plus the transported load, which varies along the tour. The expresion of the energy consumption is E = R mT (a(t) + gCr)v(t)dt. For sake of simplicity, the acceleration, the deceleration and the maximum speed are assumed known and constant.Thanks to the literature, the rolling coefficient is also known. Regarding the energy consumed between two work- stations. Three phases are distinguished according to the vehicle state. The first phase corresponds to the acceleration phase where a peak of energy is pro- duced, due to the acceleration. The second phase begins when the speed of the vehicle reach its maximum value. Finally, in the deceleration phase, the energy consumption is null. The travelled distance is directly linked to the energy although it is not the only significant parameter. Indeed, the energy consumption is different depending on the way of delivering the load. The stops at the workstations also have effects on the energy demand. Decreasing the number of vehicle stops in every workstation can reduces the number of acceleration phases, hence the energy. 3 Energy-aware mathematical modeling In this section, a mixed integer linear programming (MILP) model is presented. This model integrates the previous influential factors, and similarly to the formu- lation poposed in [1], takes advantage from a basic flow formulation. Nonethe- less, instead of taking the flow in terms of number of components into account, the mass of the shipped components is considered. We assume that only one kind of pallet can be delivered to a given workstation, each having a well-known mass. Therefore, once the mass of delivered components known, the number of components can be easily deduced. Reasoning in terms of masses is inter- esting since the energy spent for bringing a pallet to one location i to another location j is proportional to its mass. Therefore, one can considered directly inside the MILP formulation the energy cost (Cij), which represents the energy consumption for shipping one mass unit directly from i to j with j > i. The component mass brought from i to j during period t is noted M t ij. Decision variables Zt i represent the number of components left at workstation i during period t. They can easily be deduced from the values of the M t ij variables. Eventually, inventory flow variables ILt i, deduced from the Zt i values, are also modelled. 3 Using the above decision variables, the energy minimization MILP can be formulated as follows. The objective function (1) aims at minimizing the energy consumption, which is proportional to the mass M t ij traversing each arc (i,j) during period t. Constraints (2) model flow conservation together with demand satisfaction. Constraints (3) ensure that the vehicle capacity A is never exceeded and enforce variables Y t to be set to one when a tour is carried out in period t. The set of equations (4) ensures that the inventory level at workstation i never exceeds the workstation storage capacity ci. Constraints (5) enforce the difference 1 mi (P ji M t i,j) to be integral. The constraints (6) impose that the mass brought back to the depot equals the vehicle mass (0 and n + 1 being two virtual nodes associated with the depot). Constraints (7) ensure that, whether some components are delivered in workstation i during period t, the vehicle has to stop in this station at that tour. Set of constraints (8) ensure that, whether the vehicle stops in workstation i at time t, there exist an incoming and an outcoming arc selected at workstation i during period t. Constraints (9) ensure that whether there exists a mass flow between two workstations, an arc between these stations has to be selected too. Equations (10)-(12) define the domain of each variable (mmax is the maximum load that the vehicle can transport). Min z = n X i,j NT X t CijM t ij (1) st: Zt i + ILt−1 i −dt i = ILt i ∀(i, t) (2) n X i=1 Zt i ≤AY t ∀(t) (3) Zt i + ILt−1 i ≤ci ∀(i, t) (4) Zt i −1 mi ( X ji M t ij) = 0 ∀(i, t) (5) n X i=1 M t in+1 = mvY t ∀(t) (6) Zt i ≤Xt ici ∀(i, t) (7) X j>i φt ij = X j