domain: info math

text:
Walid Behiri

Sana Belmokhtar-Berraf

Chengbin Chu

Urban freight transport using passenger rail network: Scientific issues and quantitative analysis

Keywords: Urban freight, Rail transport, Paris rail network, Discrete-event simulation, Mixed Integer Program "MIP"

This paper addresses a real-life problem arising in the ongoing "Grand Paris" project. We investigate an environmentfriendly urban freight transportation alternative using passenger rail network, by providing a decision support tool for decision makers to assess the technical feasibility, the impact on services to passengers, the needs in infrastructure and hence in investment. We identify relevant scientific issues that need to be addressed in this topic at strategical, tactical and operational levels. Then we focus on the Freight-Rail-Transport-Scheduling Problem which provides valuable information to and constitutes a basis for other related problems. This problem is first formulated into a MIP. We prove its NP-hardness and hence propose a heuristic based on dispatching rules and a single-train-based decomposition heuristic. The performances of these heuristics are evaluated via employing a discrete-event simulation approach, which also provides a general framework which supports decision-makers in modelling and evaluating the dynamics of such a system for various alternative solutions under various scenarios.

INTRODUCTION

The European Union targets a carbon-dioxide-and-greenhouse-emissions reduction by 20% in 2020 from their 1990 level, in order to cope with climate change (OECD, 2014). This target has to be met in a context of population concentration in cities, e-commerce development and increase of the world population [START_REF] Comi | Exploring the Relationships between E-Shopping Attitudes and Urban Freight Transport[END_REF]. Indeed, 73% of the European population now lives in urban areas with an expected even higher rate in the future (United Nations, 2015). As a direct consequence, according to [START_REF] Van Audenhove | Urban Logistics -How to unlock value from last mile delivery for cities, transporters and retailers[END_REF], it is expected that the generated urban traffic measured in travel distance would triple by 2050, including urban goods distribution. Nevertheless, urban freight transport is necessary to support efficient economic and social development in urban areas [START_REF] Taniguchi | City Logistics -Network Modelling and Intelligent Transport Systems[END_REF]. For urban freight transport, road has been predominant despite its significant weaknesses such as worsening congestion, low safety and negative environmental impacts [START_REF] Limbourg | Optimal rail-road container terminal locations on the European network[END_REF]. A quarter of the carbon-dioxide emissions are caused by transportation activities [START_REF] Nanaki | Environmental impact assessment of electricity production from lignite[END_REF]. For several decades, although freight transport by trucks has been representing only 10% of the total traffic, it has accounted for 40% of pollutant emissions in big cities (European Cooperation in the Field of Scientific and Technical Research, 1998;[START_REF] Tang | An evaluation of the impact of the Dublin Port Tunnel and HGV management strategy on air pollution emissions[END_REF]. In many European cities, the authorities regulate urban transport through restrictive policies such as progressive ban on the most polluting vehicles, or even by introducing a toll proportional to the pollution degree of vehicles (in Milan for instance). Moreover, the European Union coordinates its actions through the Transport Committee of the EU by setting ambitious targets for member states such as zero-pollutant emissions related to goods transport in urban areas until 2030 (European Commission, 2011). In December 2015, the United Nations conference on climate change "COP21" fixed a more ambitious environmental target, which will surely have an impact on urban freight transport.

The above-mentioned context requires changes toward more environment-friendly transportation systems to cope with increasing demand for mobility in urban areas. Introducing freight transport into passenger rail network is one of the ways to absorb a significant part of the current road traffic. Goods deliveries can be ensured by combining other sustainable modes such as Electro-Mobility "E-Mobility" [START_REF] Macharis | Combining intermodal transport with electric vehicles: towards more sustainable solutions[END_REF][START_REF] Köhler | A transitions model for sustainable mobility[END_REF][START_REF] Offer | Comparative analysis of battery electric, hydrogen fuel cell and hybrid vehicles in a future sustainable road transport system[END_REF][START_REF] Van Wee | Improving Sustainability in Urban Areas: Discussing the Potential for Transforming Conventional Car-based Travel into Electric Mobility[END_REF][START_REF] Van Duin | Towards E(lectric)-urban freight: first promising steps in the electric vehicle revolution[END_REF]. The main idea here is to mitigate ground traffic by shifting as much road traffic as possible toward rail and get a better use of the currently under-exploited passenger trains' capacity. This work aims to provide a decision-support tool to investigate the feasibility and to evaluate the potential benefits and other impacts of such practices in Parisian metropolitan area. The challenge comes from coordinating freight and passenger flows using existing and forthcoming urban passenger rail infrastructure, which is actually in extension through the ambitious "Grand Paris" project. This challenging project aims to shift toward a resilient and smart city by innovating in terms of offers in services and infrastructure. The existing Parisian rail network is one of the largest in Europe and aims to add 200km rail lines and 68 stations. This project promotes sustainable development and improvement of life quality in Paris and its periphery. One of the most relevant ideas is integration of urban freight flow with the passenger one. For example, a passenger that wants to send a parcel by post should be able to deposit it at the metro/tram station before traveling. This pick-up system has been experimented in several countries and are expected to be deployed in the near future in France. The objective of this work is to take this opportunity to explore the possibility of expanding the urban rail infrastructure to freight transport, by evaluating the technical feasibility, the impact on services to passengers and financial viability, while considering technical and organizational constraints. This evaluation will enable the project managers to envision different options. For this purpose, they need a decision support tool capable of proposing optimized solutions and evaluating various alternatives under different scenarios. This paper aims to provide such a tool. The first step is to identify the scientific issues in decision-making for such a configuration, from short-term operational decisions to long-term strategical decisions. From this analysis, we investigate the Freight-Rail-Transport Scheduling Problem ("FRTSP" for short), since its solution provides valuable information to other decision-making problems and thus constitutes the basis to address such a system. For this problem, we propose a MIP formulation and several heuristics to solve the problem. A simulation model is used in order to evaluate the performance of these heuristics and the dynamics of such transportation systems which is essential for practitioners and decision makers and for academics to better understand and address the system. The remainder of this paper is organized as follows. Section 2 reviews the related literature. Section 3 is devoted to the identification of relevant scientific issues at different levels of decision making. Section 4 describes in detail the FRTSP. In section 5, the FRTSP is mathematically formulated into a MIP and its computational complexity is analyzed. Section 6 presents the solution methods: a dispatching-rule-based heuristic and a single-train-based decomposition heuristic. Section 7 describes the simulation framework we develop to model and evaluate urban freight transport using passenger rail network. In section 8, the simulation results are reported and analyzed. These results include the performance of different solution methods and the impact of freight transport on various core components of rail networks: trains, stations and rail lines. Finally, section 9 concludes the study and discusses future research directions.

LITERATURE REVIEW

Urban freight transport: road mode predominance

Freight transport in European cities is mainly related to goods flows from producers, wholesalers and distribution centers toward retailers such as stores, outlets and markets (Nuzzolo and Comi, 2014). The freight transport is still road predominant [START_REF] Lindholm | Challenges in urban freight transport planninga review in the Baltic Sea Region[END_REF]. In France, for instance, it is estimated between 85% and 90% by the National Institute of Statistics (2015). However, cities' ground transport has limited capacity and trucks cause very high level of nuisance (e.g.: noise, gas emissions, increased traffic...). [START_REF] Dablanc | Goods transport in large European cities: difficult to organize, difficult to modernize[END_REF] notes that transport-related operations in cities generate between 20% and 30% of the road traffic but, depending on the pollutant considered, it produces between 16% and 50% of air pollutants. For example, Paris statistics show that 90% of freight is carried out by trucks, representing 20% of urban traffic and 1/3 of pollutant emissions in the city (Mairie de [START_REF] De | Le transport de marchandises dans la ville de Paris. Direction de la Voirie & des Déplacements[END_REF].

The idea of mixing freight with passenger flows using urban road transportation is studied in [START_REF] Trentini | Flow management of passengers and goods coexisting in the urban environment: Conceptual and operational points of view[END_REF] where the possibility of sharing passenger buses is suggested. In particular, they analyze urban passenger and freight flows and demonstrate that there is enough room in passenger service to transport a part of the urban freight. They propose to use the spare capacity of passenger buses to transport goods from bus depots to different bus stops inside cities. This study is completed by [START_REF] Masson | Optimization of a city logistics transportation system with mixed passengers and goods[END_REF], where the authors optimize, with a mathematical model, goods deliveries from bus stops to final customers, using near-zero-emissions vehicles.

A research team working on physical internet proposes to redesign the logistics system to consider sustainability and traceability issues and goes toward an open global logistics system where supply networks are interconnected [START_REF] Sallez | On the activeness of intelligent Physical Internet containers[END_REF]. They propose to use a set of collaborative protocols, modular containers and intelligent interface standards to increase efficiency and sustainability. The principle of this approach is to pool all transport resources for commodities from different carriers between countries, cities and inside cities. The European Technology Platform ALICE plans the deployment of physical internet approach by 2050 (ALICE and ERTRAC, 2015). In spite of the potentially interesting benefit of such concepts, the physical internet requires changing current practices and infrastructures of the whole supply chain and developing new ones, which must take a very long time.

Urban underground space for freight transport: future solutions

To cope with the sustainability issue and meet the European target on CO2 emissions reduction, one interesting perspective is the use of cities' underground space to transport goods and reduce their carbon footprint. For [START_REF] Delmastro | Underground urbanism: Master plans and sectorial plans[END_REF], cities' underground capacity should be used for reducing the pressure on land use, which is mainly due to the growth in urban population. In 1991, Japanese researchers propose to develop a dedicated underground goods distribution system based on passenger rail network in order to overcome some urban environmental issues, which are related to the continuous increase of traffic congestion in Tokyo [START_REF] Kashima | Study of an underground physical distribution system in a high-density, built-up area[END_REF]. A more advanced solution is proposed by Dietrich Stein and some other researchers on a system called CargoCap (CargoCap, 2002), which consists of unmanned electric vehicles on rails that travel through underground pipelines. For [START_REF] Egbunike | Are freight pipelines a pipe dream? A critical review of the UK and European perspective[END_REF], there are opportunities for the use of underground freight transport. In January 2016, "Cargo Sous Terrain" (CST), an innovative underground goods transport solution, was launched in Switzerland [START_REF] Cst | Cargo sous terrain: The goods transport system of the future[END_REF]. It consists of developing a new distribution system by creating an underground transportation system, exclusively dedicated to freight transport among Swiss cities. The goods will be transported by autonomous electric vehicles. The feasibility study shows that this transport system is feasible both from technical and economic points of view. CST could come into operations in 2030.

Urban freight by rail as an alternative environment-friendly transportation mode

The use of rail network, equipment and infrastructure for urban freight transport is studied in some research papers. [START_REF] Dinwoodie | Rail freight and sustainable urban distribution: potential and practice[END_REF] highlights the market potential and the economies of scale of rail freight in the UK and analyses the economic and business opportunities of this environment-friendly transportation system. [START_REF] Browne | The potential for non-road modes to support environmentally friendly urban logistics[END_REF] compare rail freight activity in London and Paris (Ile de France) and report some other European initiatives in the use of rail for urban supply chain. The authors underline some difficulties and indicate the obvious benefit and potentials but without any quantitative analysis when rail becomes an environment-friendly mode for urban goods transport. Behrends (2012aBehrends ( , 2012b) ) studies an intermodal road-rail transport and identifies possible actions at a local level to improve both the competitiveness and environmental benefits. On the other hand, [START_REF] Diziain | Urban logistics by rail and waterways in France and Japan[END_REF] study the modal shift in French and Japanese urban areas to keep the best practices. They study urban logistics by rail and waterways, and conclude that the modal shift from road to these two modes is expensive and would be profitable only if many conditions are met (e.g. congested road networks, existing multimodal infrastructure, available terminals in the city center…). De Langhe (2014) analyses the role of rail in urban freight, provides a literature review, and reports a series of interviews with experts from academia and industry. In addition, this work identifies the success factors of deploying urban freight solutions by rail.

To evaluate freight transport by trams in the Parisian region, Gonzalez (2014) performs an assessment of urban rail logistics' suitability using a socio-economic cost-benefit analysis. This study shows the potential of this logistic alternative and provides the conditions to make it profitable. [START_REF] Motraghi | Analysis of urban freight by rail using event based simulation[END_REF] and [START_REF] Dampier | A study of the feasibility and potential implementation of metro-based freight transportation in Newcastle upon Tyne[END_REF], analyse urban freight in Newcastle metro system. These studies show that the concept of using an urban railway network to transport freight is viable, but it requires further research before actual implementation. As an application, [START_REF] Brice | A newly designed baggage transfer system implemented using event-based simulations[END_REF] and [START_REF] Reece | Modelling the implementation of a Baggage Transport System in Newcastle upon Tyne for passengers using Mixed-Mode Travel[END_REF] investigate transportation systems for baggage from the city center to Newcastle airport using the metro, instead of an existing baggage service. They demonstrate the feasibility of such a new baggage transfer solution and underline the higher cost than the existing service. [START_REF] Nuzzolo | Metropolitan freight distribution by railways. 5th International Conference on City Logistics[END_REF] study the possibility of delivering goods using passenger train infrastructures, between Naples and Sorrento, Italy. They propose to use existing infrastructure, such as railways and stations, and old passenger trains after removing equipment, such as seats and inside doors, to leave more room for goods. They propose to transport goods during off-peak periods. For such a solution, the mixed freight-passenger flows is limited to the use of rail track and dedicated space in stations. [START_REF] Abril | An assessment of railway capacity[END_REF] indicate that railway capacity determination depends very much on various parameters such as infrastructure, traffic, and operating parameters. They suggest to use analytical, optimization or simulation methods to overcome the system complexity. For more information on urban freight by rail, the reader may refer to [START_REF] Robinson | Urban freight and railthe state of the art[END_REF]. Based on some European examples, they realize a state-of-the-art review in urban rail freight transport.

Besides previous research papers, there are few application cases of using rail in urban logistics. There are for instance three successful implementations (MONOPRIX in Paris, New York subway and Cargo Tram in Dresden), in addition to the new project under construction in Paris called "Chapelle International". These cases are described as follows:

 Case 1: MONOPRIX in Paris [START_REF] Dablanc | Freight transport for development toolkit: Urban freight[END_REF]

& (MONOPRIX, 2007)

MONOPRIX is a French supermarket chain, SNCF (Société Nationale des Chemins de Fer français, the largest French rail operator) has been delivering a small part of goods to some supermarkets of this chain. This is done using the commuter line D (RER D) in Paris, for the transport of a number of goods such as soft drinks, textiles, cosmetics, household goods, and leisure products, from MONOPRIX warehouses outside Paris (Combs-la-Ville and Lieusaint) to Bercy station inside Paris. Thereafter, the products are transported to stores by trucks running on NGV fuel (Natural Gas Vehicle), to comply with the emissions reduction principle along the logistics line. This is a quite large-scale implementation, since this line is 30 km long and can carry 210 000 pallets (equivalent to 120 000 tons) each year, with 5 trains of 20 cars per week (one daily train in the morning).  Case 2: New York subway (Metropolitan Transportation Authority, 2014) This case concerns the subway waste collection in New York City through stations using modified subway cars. The collect is done overnight, and as the New York subway runs 24/7, it is mixed between freight transport (waste in this case) and passenger transport. This solution enables the collect of 14 000 tons of waste per year, with 11 dedicated subway trains, covering 359 stations with 567 stops.  Case 3: Cargo Tram of Dresden [START_REF] Quak | Sustainability of urban freight transport. Retail distribution and local regulations in cities[END_REF] A portion of 4 km tram line in Dresden is used to transport automotive parts and modules, from a Volkswagen warehouse near a rail terminal in the city, toward their factory located in the city center. This solution can cope with limited storage space in order to ensure daily production. This line can deliver 300 000 tons of products per year with 10 daily trips, which significantly reduces CO2 emissions.

 Case 4: Chapelle International (SOGARIS, 2016)

This is a global urban logistic solution based on an urban rail shuttle and the multi-modal logistics hub "Chapelle International" (under construction). An important warehouse located in the north of the "Ile-de-France" region (Greater Paris region) is interconnected to "Chapelle International" with a railway. Goods will be transported by trains and each train will transport 60 mobile boxes. Thereafter, trucks running on NGV fuel would carry the products to stores. This solution will save nearly 10 000 trucks per year in the center of Paris.

Optimization techniques for freight and rail problems

Many researchers have proposed such models for freight transport (by road, rail, sea or air), and particularly addressed the complexity generated by urban freight. [START_REF] Crainic | Planning models for freight transportation[END_REF] identify and present the main issues encountered at various decision-making levels (strategic, tactical and operational) in freight transport planning and operations, and give an overview of appropriate operations-research-oriented models and methods.

Planning optimization is addressed using mathematical programming in the works of [START_REF] Gao | Three stage optimization method for the problem of scheduling additional trains on a high-speed rail corridor[END_REF] who provide a bi-objective MIP model to adjust train timetable in order to insert new trains in high-speed rail corridor. A three-stage optimization method is proposed. The first stage minimizes the travel time of each new train. In the second stage, the deviation of existing trains are minimized. Finally, the third stage minimizes the total travel time of the additional trains. Another application of ILP (integer linear programming) is also suggested by [START_REF] Besinovic | An integrated micro-macro approach to robust railway timetabling[END_REF] to provide a robust train plan for the Netherlands rail network. An integrated iterative micro-macro approach is proposed to determine stable and robust railway timetables to face the increasing demand for passengers and freight transport.

For long-haul transportation of containerized goods (in heterogeneous boxes) where automated terminals are used for metro-cargo through a complex rail network, [START_REF] Anghinolfi | Freight transportation in railway networks with automated terminals: A mathematical model and MIP heuristic approaches[END_REF] study the offline planning of customer requests so that each request which may involve several boxes has to be assigned to a single route a route composed of several segments crossed by trains. The set of routes are determined in advance. Hence, boxes travel from a departure terminal to their arrival by transshipment, considering the loading and packing of boxes in train wagons. The authors propose a 0-1 linear programming formulation to solve this NP-hard generalized assignment problem. They develop two metaheuristics operating with a MIP solver to obtain near-optimal solutions. For bulk commodity deliveries by rail, [START_REF] Lawley | A time-space scheduling model for optimizing recurring bulk railcar deliveries[END_REF] developed a MIP model considering customer demand, rail network characteristics (the routes between every origin-destination pair), loading/unloading hours in stations for each customer demand, the maximum number of trains simultaneously in each station for loading/unloading operations, etc. The objective is to maximize the satisfied demand while minimizing the total waiting time at stations. Unlike our study where the train schedule is predefined, they aim to determine the best train schedule by avoiding saturation at rail tracks and stations.

Optimization or simulation models have also been used to solve urban transportation problems. [START_REF] Russo | A modelling system to simulate goods movements at an urban scale[END_REF] present recent developments in simulating urban goods flow. They propose a modelling system capable of assessing ex-ante measures and linking consumers' and retailers' choices. Inspired from a vehicle-routing problem, [START_REF] Figliozzi | Analysis of the efficiency of urban commercial vehicle tours: Data collection, methodology, and policy implications[END_REF] develops a simulation tool for measuring the economic impact of urban commercial vehicle tours. In a later work, [START_REF] Figliozzi | The impacts of congestion on commercial vehicle tour characteristics and costs[END_REF] studies the impact of congestion on indicators such as costs of commercial vehicle tours. [START_REF] Benjelloun | Trends, challenges, and perspectives in city logistics[END_REF] present an overview on concepts, models, and planning issues in city logistics and identify trends, challenges, and research directions. Their work is based on an analysis of a large number of projects and proposals. [START_REF] Fatnassi | Planning and operating a shared goods and passengers on-demand rapid transit system for sustainable city-logistics[END_REF] study the sharing of goods and passenger transport using a rapid transit system, a sort of automated guide-way transit composed of small battery-fed electric vehicles and dedicated transport lines. They propose two mathematical formulations to model the problem with the objective of minimizing the average number of empty moves per period, considering some specific constraints such as the battery capacity and recharges. However, the main problem considered is determining the vehicle routes between stations. They use a dynamic optimization approach and develop algorithms to solve the dynamic problem and demonstrate the applicability of this transportation mode.

Summary

This literature review shows that freight transport, especially in urban areas, is shifting toward innovative and sustainable solutions with crucial environmental challenges. Some of them, such as CargoCap or CST, are designed for far future, due to the technological obstacles and heavy investment they require. Existing literature shows interesting perspectives of using underground for freight transport, especially in crowded large cities with advanced rail networks. Optimization techniques (such as mathematical modelling, heuristics and metaheuristics, …) are used to solve various transportation problems (scheduling, routing, assignment, …). This paper considers scheduling of goods transport using passenger trains. In this context, various constraints have to be taken into account such as waiting time in stations, spare space available inside trains. Especially train routes and timetables are predefined. The literature review shows that no work has even been carried out considering all these features. Furthermore, the goods to transport could be any nature, as soon as they are packed into standard-size boxes as recommended by physical internet [START_REF] Sallez | On the activeness of intelligent Physical Internet containers[END_REF].

Before implementing such a transportation mode, several issues at different decision-making levels must be identified and addressed. This paper identifies these issues and then focuses on one of them, which is the basis of all related issues, by using mathematical modelling and quantitative analysis for the decision-making. This decision-making process consists of assessing various alternatives regarding existing and soon-available technologies and infrastructure. As a consequence, this paper contributes to the field of urban freight by rail in three aspects:  First, as reported in the literature, relatively little work has been devoted to urban freight by rail. As indicated by [START_REF] Comi | Modelling challenges to forecast urban goods demand for rail[END_REF], only few studies have explored modelling freight demand for rail in urban context. This paper seems to be the first to address such a system by identifying the scientific issues at different decisionmaking levels that need quantitative analysis  Second, to the best of our knowledge, this paper is the first to formulate the goods transport using urban passenger rail network into a MIP and solve it efficiently.  Finally, it develops a simulation model which is crucial to evaluate and analyse ex ante the impact of introducing freight transport service into the passenger one.

STRATEGICAL, TACTICAL AND OPERATIONAL ISSUES IN URBAN FREIGHT TRANSPORT WITH PASSENGER RAIL NETWORK

In this section, we investigate the global problem of integrating urban freight transport into passenger rail network and identify major issues that need to be addressed both from scientific and operations points of view at various decisionmaking levels. This will not only position the main topic of this study into its real-life context but also shows its relevance to further address other issues.

Urban rail network has two important specificities, with respect to road transportation networks:  All lines are physically independent in terms of infrastructure and operations.  There are indirect interconnections between certain lines, through connection points with possible transshipment.

A hypothetical example shown in Figure 1 illustrates goods transportation using the Paris urban rail network. This example shows the important coverage potential when several rail lines are used. This route is composed of two sequential segments corresponding to two lines (D and E). Each segment corresponds to a portion of the route using a single line and a single train.

Figure 2 presents nine interrelated subproblems dealing with the global issue, from long-term strategic decisions to short-term operational ones. These problems are numbered from strategical level to operational level.

 At the strategic level:

o Storage-space-sizing in stations: Problems 1 and 2 in Figure 2 define the appropriate space needed to store goods before and after their transport by train. This long-term decision should be studied for the new stations that are to be built in the "Grand Paris" project. This issue is crucial since it becomes very expensive to expand these areas once it is built. In order to accurately determine the size of these storage areas, many data should be collected. In particular, the needed information is related to the forecast of the potential demand and supply, the potentially available area in existing stations, the definition of the transport process to evaluate the time spent by goods in stations before and after the transport…

A part of Paris rail network (RATP)

 At the tactical level: o Trains frequency and sizing: It is noted as problem 3 and it determines the number of railcars to purchase for freight transport and the frequency of these cars must be used on a daily basis. This frequency must be quite stable over time. For the time being, it is impossible to transform a passenger car into a freight one or reversely. In the future, it will certainly be possible to design flexible railcars to serve passengers in peak periods and freight in off-peak periods. But such cars will certainly have a higher purchase cost than dedicated ones and cost more during the operating phase because of the additional cost for adjustment. In any case, the number of cars of each type (flexible or dedicated) must be decided as accurately as possible in order to maximize profitability. However, the number of cars in trains allocated for freight during a period can be fixed or variable. For example, it could be interesting to dedicate more space to freight when the passenger traffic is less important (e.g. on weekend mornings). At the opposite, there can be fewer or even no cars dedicated to freight when passenger traffic is important such as weekend evenings.

 At the operational level: o 2D/3D bin packing problem: Problems 4 and 5 in Figure 2 are related to the temporary storage areas. These problems aim to: 1-optimize the use of space in order to maximize the number of transported boxes, 2-minimize the material-handling operations. o Train timetabling: it is problem 6 which is to determine the optimal timetable of trains during an operating period. To adjust the goods transport capacity during a period, the planning should be defined in terms of number of trains that should be planned whereas their starting and arrival times are determined. The timetable could be very close to the one without freight transport since there is a very strong constraint about the impact on passenger traffic. However, it should be regularly recomputed regarding to freight demand and updated if necessary in order to respond to new freight demand. o 2D/3D bin packing problem in freight cars: Problem 7 is one of the most difficult one. Indeed, the main difficulty lies in choosing the best place for a box that has just been loaded into the train in order to facilitate its handling when unloading it later so that as many as boxes will be loaded in the meantime. o Goods delivery in the departure station: Problem 8 regulates the upstream flow (inbound goods flow at the departure rail-station). Hence, the transport company would like to maximize the goods volume during an operating period, in accordance with the transport capacity of the whole system. The main issue here is to regulate the upstream flow so that the transport company could propose a commercial offer with different rates to balance the demand arrivals within a day. For example, it could be relevant to charge less for goods transport during off-peak periods. The load balance could also be performed among stations so that if an important volume arrives to one station, some boxes could be loaded in other stations to smooth working load regarding to stations' capacity. o Freight Rail Transport Scheduling or Dispatching: This problem noted as problem 9 determines the time and the train to load each demand so that the total waiting time is minimized. The waiting time of a demand is measured as the difference between the time it is loaded into the train and the time it arrives at its departure station (called arrival time or ready-for-departure time). This goal allows to maximize the turnover of goods in stations which is equivalent to minimizing the temporary storage area in the stations. In this problem, several technical and operational constraints or parameters must be taken into account such as the time / space limits for the goods loaded into the trains. The results of this problem are essential to solve other problems such as problems 1, 2, and 3.

This paper focuses on the Freight Rail Transport Scheduling Problem. The main contribution is to provide decision makers with a tool enabling them to evaluate and assess, through quantitative analysis and discrete-event simulation, the impacts on various aspects under various scenarios, of integrating freight flow with passenger one. Moreover, since the traffic of passengers remains the priority, this new service could be relevant only if it does not disturb the passenger traffic. Furthermore, the "Grand Paris" project with new lines and stations focuses on the capacity of trains to transport this freight flow since the size of stations, hence the temporary storage area, is not fixed yet. However, it is important to evaluate the additional investment for plausible scenarios. That is why optimization tools as well as simulation tools are necessary to optimize the use of resources on the one hand and evaluate the additional resources required under various scenarios on the other hand. Sections 4, 5 and 6 are dedicated to the description of the FRTSP, the optimization models and methods for the use of resources. And Section 7 describes the simulation environment that can be used to not only evaluate the performances of these models and methods but also provide information about the impact of additional resources.

FREIGHT RAIL TRANSPORT SCHEDULING PROBLEM: DESCRIPTION AND ASSUMPTIONS

The current Paris rail network is already complex with three modes described as follows:

 The subway, covering mainly the city center, has a network of 220 km and serving 302 stations.  The tram which is actually around the city center and in some departments of "Ile de France" (outskirts of Paris), with a network of 104 km and serving 181 stations.  The commuter rail (RER) linking the localities of "Ile de France" to Paris city center, with a network of 587 km and serving 257 stations.

All these three transport modes are characterized by the following physical components:  Stations: there are three types of stations: underground stations, at ground level stations and elevated stations.  Railway: same as for stations.

 Trains: subways or metro, trams and suburban or commuter trains.

Mixing freight with passenger transport using rail network involves the sharing of at least one of these resources.

In the remainder of the paper, we consider the complete sharing of these three physical components. Consequently, the operating time is also shared since some trains will transport freight and passengers simultaneously. Indeed, with passengers in the train, the travel must meet the operating constraints for passenger transport, such as the strong limits on the stopping time at stations. Moreover, the current legislation in France forbids conflating freight with the passenger transport in a same car for various reasons. Consequently, it is proposed to reserve some cars at the end of trains for freight with a separate and inaccessible space dedicated to freight loading/unloading operations. In this case, the sharing would be more appropriate during off-peak periods to avoid loading/unloading goods when the stations are crowded.

The FRTSP considers a single line in the rail network illustrated in Figure 3. On this line, 𝑆 passenger stations can be used for loading and unloading goods and the travel time between two successive stations is known and fixed. The goods are packed in identical standardized boxes. All trains are able to transport goods with a pre-determined capacity which is expressed as the maximum number of standardized boxes. Goods correspond to customer orders or demands. Each order or demand may involve different number of boxes. The orders have independent ready-for-departure times at the departure station. Figure 3 provides an illustration of this problem, showing the demands and train queues. In this paper, we only consider the problem involving a single rail line. The approaches can be used when several lines are involved, since the lines are independent one of another, except at connecting stations. This extension can be done by solving a coordinating problem which consists of synchronizing the transhipment operations with usual loading/unloading operations.

We make the following assumptions and introduce some notation for the FRTSP:  Transport demands are known in advance and there are 𝐽 of them per day.  Goods are put in standardized boxes. Although each customer may require different products in different quantities, standardization of boxes allows to measure the transport demand of each customer in number of boxes. The number of boxes of demand j is noted 𝑄 𝑗 .  Demand j becomes ready for departure from its departure station at time 𝑟 𝑗 , called ready-for-departure time.  Goods transport takes place during off-peak periods.  The train departure time from station 1 is known in advance, it is given by 𝑙 𝑡 for train t. T trains are available to connect S stations through the line during the day.  The capacity allocated for goods in train 𝑡 is given by 𝑐𝑎𝑝 𝑡 . If a train is fully dedicated to passenger transport, it must be eliminated from the input timetable for passenger transport.  The time needed for loading and unloading each box is considered as the same and is noted h, independent of demands, trains, and stations.  Any station of the line is a potential station to load or unload goods. So, the goods have to be delivered to their respective departure stations and recovered from their respective arrival stations.  The storage area for departing demands at each station s is of limited capacity Cs in terms of maximum number of boxes stored simultaneously, even though this capacity is set to a very large value in the experiments to investigate new lines and new stations. Actually the rail-network operator is more concerned by train capacity in this context.  When a demand arrives at its destination, it is immediately evacuated from the station. As a consequence, there is no need to consider storage capacity for arriving demands  The travel time between two successive stations is considered to be known and given by 𝑡𝑡 𝑠 .  The maximum waiting time of a train at each station is given by Wait max .  The minimum waiting time which is necessary to board passengers at each station is known and fixed, it is 𝑊𝑎𝑖𝑡 𝑚𝑖𝑛 . Without loss of generality and for the sake of convenience, the demands are assumed to be numbered in nondecreasing order of the ready-for-departure times; in other words, Train Queue

𝑟 1 ≤ 𝑟 2 ≤ ⋯ ≤ 𝑟 𝐽

t=1 ( ) t=2 ( ) t=T ( )

A MIXED INTEGER MATHEMATICAL PROGRAMMING MODEL AND COMPLEXITY ANALYSIS

The problem described above can be formulated into a mixed integer program as follows.

𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 ∑ ∑ (𝑅 𝑗 -𝑟 𝑗 𝑥 𝑗,𝑡,𝑑 𝑗 ) 𝑇 𝑡=1 𝐽 𝑗=1

(1) subject to

∑ 𝑥 𝑗,𝑡,𝑑 𝑗 𝑇 𝑡=1 = 1 𝑗 = 1,2, … , 𝐽 (2)
𝑥 𝑗,𝑡,𝑠 -𝑥 𝑗,𝑡,𝑠+1 = 0 𝑠 ∈ [𝑑 𝑗 , 𝑎 𝑗 -1], 𝑗 = 1,2, … , 𝐽

∑ 𝑥 𝑗,𝑡,𝑠 𝑗∈𝐽 𝑠 × 𝑄 𝑗 ≤ 𝑐𝑎𝑝 𝑡 𝑡 = 1, … , 𝑇, 𝑠 = 1, … , 𝑆 (3)
𝑥 𝑗,𝑡,𝑑 𝑗 × 𝑟 𝑗 ≤ 𝑙 𝑡 + ∑ (𝐶 𝑡,𝑠 ′ + 𝑡𝑡 𝑠 ′ ) 𝑑 𝑗 -1 𝑠 ′ =1 𝑗 = 1, … , 𝐽, 𝑡 = 1, … , 𝑇 (4)
𝐶 𝑡,𝑠 ≥ 𝑊𝑎𝑖𝑡 𝑚𝑖𝑛 𝑡 = 1, … , 𝑇, 𝑠 = 1, … , 𝑆 (5)
𝐶 𝑡,𝑠 ≥ ∑ ℎ × 𝑄 𝑗 𝑥 𝑗,𝑡,𝑠 𝑗∈𝐽 ′ 𝑠 𝑡 = 1, … , 𝑇, 𝑠 = 1, … , 𝑆 (6)
𝐶 𝑡,𝑠 ≤ 𝑊𝑎𝑖𝑡 𝑚𝑎𝑥 𝑡 = 1, … , 𝑇, 𝑠 = 1, … , 𝑆 (7)
𝑅 𝑗 ≥ 𝑙 𝑡 + ∑ (𝐶 𝑡,𝑠 ′ + 𝑡𝑡 𝑠 ′ ) 𝑑 𝑗 -1 𝑠 ′ =1 -𝑀(1 -𝑥 𝑗,𝑡,𝑑 𝑗 ) 𝑗 = 1, … , 𝐽, 𝑡 = 1, … , 𝑇 (8)
𝑅 𝑖 ≤ 𝑟 𝑗 + 𝑀𝑦 𝑖,𝑗 𝑖 ∈ 𝐷 𝑗 , 𝑗 = 1, … , 𝐽 (9)
∑ 𝑦 𝑖,𝑗 𝑖∈𝐷 𝑗 × 𝑄 𝑖 ≤ 𝐶 𝑑 𝑗 -𝑄 𝑗 𝑗 = 1, … , 𝐽 (10)
𝑥 𝑗,𝑡,𝑠 ∈ {0,1}, 𝐶 𝑡,𝑠 ≥ 0, 𝑅 𝑗 ≥ 0 𝑡 = 1, … , 𝑇, 𝑠 = 1, … , 𝑆, 𝑗 = 1, … , 𝐽

𝑦 𝑖,𝑗 ∈ {0,1}, 𝑖 ∈ 𝐷 𝑗 , 𝑗 = 1, … , 𝐽 (12)
where 𝐽 𝑠 = {𝑗|𝑑 𝑗 ≤ 𝑠 < 𝑎 𝑗 } and 𝐽′ 𝑠 = {𝑗|𝑠 ∈ {𝑑 𝑗 , 𝑎 𝑗 }} represent the set of demands needing to pass by station s and the set of demands such that station 𝑠 is either a departure or an arrival station, respectively.

In this model, the objective function expresses the minimization of the total waiting time of all demands in their departure stations. Constraint set (2) assigns each demand to exactly one train at its departure station. Constraint set (3) imposes train continuity for each demand so that each demand's transport is ensured to be performed by the same train throughout the portion of the line between its departure and arrival stations. Constraint set (4) deals with the capacity or space limit in the train. Since at arrival stations goods are unloaded from the train, constraint set (4) considers only those remaining in the train. Constraint set (5) respects the arrival times of demands, so that a demand can only be assigned to a train arriving later at the departure station of the demand. Constraints sets (6), ( 7) and (8) determine the waiting time of train t at station s. Constraint set (9) determines the earliest time at which demand j is loaded into train t. Constraints (10) ensure the consistency of the definition of yi,j. For any couple of demands 𝑖 and 𝑗 such that 𝑖 ∈ 𝐷 𝑗 , if 𝑖 departs after demand 𝑗 becomes ready for departure; i.e., 𝑅 𝑖 > 𝑟 𝑗 , constraints (10) require that 𝑦 𝑖,𝑗 = 1, which is consistent with the definition. Constraints (11) expresses the storage capacity at each station. When demand 𝑗 becomes ready for departures at its departure station, the number of boxes that are available but have not yet been loaded must not exceed the storage capacity of this station.

The computational complexity of this problem can be evaluated by considering the following special case:  All demands are available at time 0, at the same departure station with the same arrival station: 𝑟 𝑗 = 0, 𝑑 𝑗 = 1 and 𝑎 𝑗 = 2, ∀𝑗 ∈ 𝐽.  Each demand should be transported by exactly one train.  Trains' timetable is known in advance together with the frequency of trains.  The travel time between the departure and arrival stations is the same for all trains regardless of the number of loaded boxes.  The trains can carry several demands at the same time, but with a limited capacity.  The waiting time of trains at stations is unlimited.  The storage capacity at the stations are unlimited In this special case, the waiting time of demand j is equal to the departure time of the train it is loaded into. The previous MIP model with these assumptions becomes:

𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 ∑ ∑ (𝑥 𝑗𝑡 × 𝑙 𝑡 ) 𝑇 𝑡=1 𝐽 𝑗=1 (14) ∑ 𝑥 𝑗,𝑡 𝑇 𝑡=1 = 1 𝑗 = 1, 2, … , 𝐽 (15)
∑ 𝑄 𝑗 × 𝑥 𝑗,𝑡 𝐽 𝑗=1 ≤ 𝑐𝑎𝑝 𝑡 𝑡 = 1,2, … , 𝑇 (16)
𝑥 𝑗𝑡 ∈ {0,1} 𝑗 = 1, 2, … , 𝐽, 𝑡 = 1,2, … , 𝑇 Thus, the problem of transporting goods as soon as possible is reduced to a generalized assignment problem, where the objective is to minimize the total cost of assigning J jobs to T agents ( 14), so that each job, which corresponds to a demand, is assigned to exactly one agent, which corresponds to a train in our case (15), subject to the capacity constraints of the agents -"trains" (16). Because the generalized assignment problem is NP-hard [START_REF] Fisher | A multiplier adjustment method for the generalized assignment problem[END_REF], the studied problem is therefore also NP-hard.

SOLUTION METHODS TO THE FRTSP

Because of the NP-hardness of the FRTSP, it cannot be solved in a reasonable amount of time for real-life instances which are often very large. On the other hand, the problem being at an operational level, it requires a very short response time. Furthermore, the decision must be frequently recomputed, due to random events, for instance, that render the decision made previously far from optimum and even infeasible. Therefore, heuristics that require very short computation times, which is a major issue for practitioners in addition to their ease of understanding regarding the solution-building process, are commonplace in industry for operational decision making. In the following subsections, we propose two heuristics.

Both heuristics assign the demands into the trains so that the following operating constraints are ensured:  The limits on the waiting time of each train in each station.  The train capacity.  The arrival time of each demand at its departure station.  The travel time of trains through the line.  The storage capacity at each station Both heuristics consider the trains one after another in the order of their arrivals at station 1 and a single train is considered in each iteration. The difference between them lies in the way of selecting the demands at each station to be loaded into the considered train. One of them, called BDH for best-dispatching-rule heuristic, consists of using three dispatching rules and then selecting the best among the obtained solutions. The other, called STH for single-train-based heuristic, optimally selects the demands to load into the train. We now describe each of these heuristics, we only focus on how to select the demands to load into the considered train.

Heuristics based on dispatching rules

When a train is considered, the stations are examined from upstream to downstream in the order of 1, 2, …, S. At each station s, we identify the set of demands that can be loaded into the train; in other words, the demands in this set must satisfy the following conditions:

1. It has not been loaded into earlier trains 2. Station s is their departure station 3. They are available at the time when the train arrives at station s Then some of these demands are selected to be loaded into the train according to one of three dispatching rules. In practice, the before-mentioned set of demands are arranged into a list in decreasing order of the priority defined by the dispatching rule. This list of demands is then scanned, and the first demand in the list such that the remaining capacity and the remaining waiting time of the train are sufficient to load it is actually loaded into the train and then removed from the list.

The dispatching rules considered are the following:  FIFO: The earlier a demand becomes ready for departure, the higher priority it has. The idea is to avoid waiting of the demands.  Largest-volume-first: The more boxes a demand involves, the higher priority it has. The underlying idea is to occupy as little as possible the storage areas in the stations.  Smallest-volume-first: The fewer boxes a demand contains, the higher priority it has. The intuitive idea is that the smallest demands have the highest chance to be transported and this allows to transport the most demands as quickly as possible.

Single-train-based heuristic

One shortcoming of the previous rule-based heuristic is its myopic nature, since each demand is loaded into a train without considering other demands especially those at the downstream stations. In addition, regarding the combinatorial nature of the problem, the solutions obtained with this heuristic are very likely to be far from being optimal. We therefore develop a more elaborate method with some looking-ahead attitude. As shown previously, the problem is NP-hard and fast algorithms are needed for large instances. The complexity of the problem is related to the numbers of demands, trains and stations. Nevertheless, if the single-train-related subproblems are small enough to be solved into optimality, which is the case in the experiments reported in Section 8, it is preferable to do so. In this case, we should not consider the stations separately. We therefore identify the set of demands Ω 𝑡 satisfying the following conditions:

1. They have not been loaded into earlier trains 2. They are available when the train arrives at their respective departure station: 𝑟 𝑗 ≤ 𝑙 𝑡 + ∑ (𝑊𝑎𝑖𝑡 𝑚𝑎𝑥 + 𝑡𝑡 𝑠 )

𝑑 𝑗 -1 𝑠=1

So-defined sub-problem related to a single train t can be formulated as follows.

𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒

𝐶 𝑠 ≥ 𝑊𝑎𝑖𝑡 𝑚𝑖𝑛 𝑠 = 1, … , 𝑆 (22)
𝐶 𝑠 ≥ ∑ ℎ × 𝑄 𝑗 𝑥 𝑗,𝑠 𝑗∈𝐽 ′ 𝑠 𝑠 = 1, … , 𝑆 (23)
𝐶 𝑠 ≤ 𝑊𝑎𝑖𝑡 𝑚𝑎𝑥 𝑠 = 1, … , 𝑆 (24)
𝑅 𝑗 ≥ 𝑙 𝑡 + ∑ (𝐶 𝑠 ′ + 𝑡𝑡 𝑠 ′ ) 𝑑 𝑗 -1 𝑠 ′ =1 -𝑀 (1 -𝑥 𝑗,𝑑 𝑗 ) 𝑗 ∈ Ω 𝑡 (25) ∑ (1 -𝑥 𝑖,𝑑 𝑖 ) 𝑖∈𝐷 𝑗 ∩Ω 𝑡 × 𝑄 𝑖 ≤ 𝐶 𝑑 𝑗 -𝑄 𝑗 𝑗 ∈ Ω 𝑡 (26) 𝑥 𝑗,𝑠 ∈ {0,1}, 𝐶 𝑠 ≥ 0, 𝑅 𝑗 ≥ 0 𝑗 ∈ Ω 𝑡 , 𝑠 = 1, … , 𝑆 (27)
Note that constraint (18), which comes from constraint (2), is an inequality, instead of an equality as in (2), because we cannot require all the demands in Ω 𝑡 to be loaded into train t. Because of this constraint, as it is, there is a trivial optimal solution to this single-train-related subproblem defined by ( 17) to ( 27), by setting all decision variables to 0; in other words, by loading no demand at all! Obviously, this is not what we are looking for, since the most important resource the trainwould not be used. Actually, an (even more) important objective function which is maximizing the number of transported demands is missing in this model. That is why for each train t, instead of solving the problem defined by ( 17) to ( 27), we add a primary objective aiming to maximize the number of transported demands, to transform the problem into a bi-objective decision-making problem. To be more specific, this problem can be rewritten as follows. where 𝜔 is the optimal objective value of Problem P1. Both problems P1 and P2 being single-objective MIPs, they can be solved using standard MIP solvers such as CPLEX. Note that solving P1 and P2 using CPLEX can solve to optimality the problem defined in (28) and ( 29) which is related to a single train. The concatenation of so-obtained solutions to single-train subproblems cannot be guaranteed to be optimal to the problem defined by (1)---(13) because of the decomposition. That is why it is only a heuristic.

PROBLEM MODELING AND SIMULATION USING ARENA

This section describe the simulation model we develop, on the one hand, to fulfil operational requirement for practitioners, and on the other hand, to make sure, from an academic point of view, that the mathematical model is close to the reality and to evaluate and simulate the dynamics, the behavior of the system. From an operational standpoint, a full-scale experimentation in real life would need a heavy investment in terms of finance, time, disturbances and risks. Computer simulation is therefore essential to anticipate various scenarios. Furthermore, simulation models are also widely used in academic research by combining them with other tools [START_REF] Borodin | Optimisation et simulation d'une chaine logistique : application au secteur de l'agriculture[END_REF] as we do here. Actually, mathematical models often require explicit expressions of constraints and objectives in decision variables, which is not always possible. Simulation can then be used to evaluate these indicators. Furthermore, mathematical models cannot take into account all the aspects of a problem then simulation is a very useful complement, especially when some parameters are not accurate.

As [START_REF] Dessouky | A simulation modeling methodology for analyzing large complex rail network[END_REF] put it, "the rail networks are complex, compound delays and ripple effects from conflicts at complex junctions, stations, and railroad-railroad crossings at grade and other factors in some rail networks make it difficult to develop analytical models to study delays and capacity". [START_REF] Motraghi | Analysis of urban freight by rail using event based simulation[END_REF] explain that "the complexity of the real world systems makes it hard for analytical models to provide clear analysis and are often not economically viable to use. On the other hand, simulation models enable low-cost experimentation and the modeling of this complexity which can lead to accurate results and conclusions".

Simulation for rail transport was studied by [START_REF] Motraghi | Analysis of urban freight by rail using event based simulation[END_REF], [START_REF] Grube | An event-driven simulator multi-line metro systems and its application to Santiago de Chile metropolitan rail network[END_REF], [START_REF] Dessouky | A simulation modeling methodology for analyzing large complex rail network[END_REF], [START_REF] Marinov | Concepts, models and methods for rail freight and logistics performances: an inception paper[END_REF]. Several specific simulation software packages are available for modeling and simulating rail networks [START_REF] Furtado | ICT and management tools for railway freight[END_REF], such as Rail Traffic Controller, Open Track and Railsys. However, to consider the queuing nature of the FRTSP, discrete-event simulation software packages are more suitable. ARENA, WITNESS and SIMUL 8 are such tools.

In this study, we develop a very general framework to model rail networks. This framework can be easily adapted to all cities. We take advantage of this framework to model all issues related to rail network, especially the FRTSP we focus on in this paper. ARENA Software is used for this purpose. For more information about this software, the reader may refer to [START_REF] Rossetti | Simulation Modelling and Arena[END_REF] or [START_REF] Altiok | Simulation modeling and analysis with ARENA[END_REF]. One major reason for this choice is its ability to consider all the identified technical and operational constraints. In addition, the compatibility with a programming script such as Visual Basic (VBA) allows implementing various decision-making problems defined at the beginning of the paper. The developed model for FRTSP is composed of three parts as shown in Figure 4 and described hereafter.

Part 1: Freight transport demand generator

This part of the model generates J demands during the pre-operating period. For each demand j, the following characteristics are generated according to a given probability distribution: the departure station, the arrival station, the arrival or ready-for-departure time at its departure station, and the number of boxes required to pack it.

All generated data are saved in a "demand" matrix in VBA environment. During an operating period, at its arrival time, a demand is added to the queue of its departure station, in order to be transported.

Part 2: Train generator

This part of the model generates a timetable involving T mixed freight / passenger trains during an operating period while making sure that the timetable is periodic. To simulate the timetable of trains for the next operating period, all trains are generated at the same time (they are not dynamically generated).

VBA block is used to save all parameters for the subsequent calculations. ARENA blocks Queue, Seize, Delay and Release simulate the process of train arrivals into the railway line according to the timetable. The time at which train t is introduced into the line is calculated in the delay block according to the operation: 𝑙 𝑡 -𝑙 𝑡-1 .

Part 3: Railway line

This part of the model represents the railway line that is composed of:  Railroads (or interconnection line "rail" in Figure 4): modeled by a "DELAY" block that expresses the time required to travel the distance between two successive stations.  Stations: this is the physical place where the trains stop to board passengers and load / unload goods. Depending on the freight load in the train and the algorithm implemented in the Arena VBA blocks, the boxes in this station are loaded or not. Thus, depending on the number of boxes to be transported, the waiting time of train t at station s is calculated and saved in the delay block of the ARENA block "stationS" which is a dynamic Arena process.

EXPERIMENTAL STUDY AND SIMULATION

One of major difficulties when studying a new system, including the one investigated in this work, is the lack of data such as freight demand because of the absence of historical data. However, to run a simulation model, instances are needed and should be as realistic as possible. In this experimental study, we use instances generated randomly but on the basis of some available data such as trains' timetables and capacity. For the other parameters, random values are generated on the basis of transport company projections. The simulation model aims to evaluate the performance of the transportation system under study when optimized decisions are integrated into the system's dynamics. As the studied problem is NP-hard, in order to compare the performance of heuristics with the optimal solution, the instances' size must be reasonable (simulation duration, number of demands, trains and stations). The simulation process provides an important stream of output which is reported and analyzed.

Simulating parameters and instance generation

A typical line is considered with ten stations which are indexed from 1 to 10. The goods travel through the line from the lowest-indexed station to the highest one. The duration of the simulation is 300 minutes during which there are 30 trains which pass through the line with a frequency defined as one train every 10 minutes. The capacity allocated to freight in any train is 15 boxes representing 30% of the total train capacity. The travel time between two successive stations is estimated at 5 minutes. The maximum waiting time of a train at any station is 1 minute and the minimum waiting time for passenger boarding is 30 seconds. The time required to load or unload each box is 10 seconds. For the other parameters, they are generated as follows:  The arrival (or ready-for-departure) times of demands are generated using a uniform distribution 𝑟 𝑗 ∈ 𝑈 [0,240] minutes where 0 corresponds to the initial time which could be 10 am for instance. The upper bound fixed to 240 minutes corresponds to the latest possible arrival time for any demand.  Demand sizes "𝑄 𝑗 ": the size of a demand is between 1 and 5 (𝑈 [1,5]) measured in number of standard boxes.  Departure and arrival stations: randomly generated between the first station and the last one for each demand.

Numerical results

The experiments are run on an Intel Xeon CPU E3-1245 v3 @ 3.40 GHz with 8 GB RAM. The simulation software used is ARENA version 14.7. CPLEX 12.5 is used for MIP solving. Default parameters are used for the experiments. BDH is implemented in VBA and is launched when the entity "train" passes through VBA block before each station. Thus, the demands to be transported from this station by the current train are identified and their loading is performed when the entity "train" stops in the corresponding station (ARENA block "stationS").

The generated instances are classified into categories according to the number of demands. Each category is composed of 25 instances. The computational results for each category are reported in Table 2 which gives the mean value of the average waiting time (in seconds) per demand over the 25 instances of that category. This table clearly shows a direct correlation between the waiting time and the number of demands. Regarding the MIP model, it quickly finds optimal solutions for the instances with up to 50 demands (the solutions are found in less than 1 second). For the instances with up to 100 demands the average computation time is less than 15 seconds, even though the computation time is as long as about 90 seconds for one of the instances with 100 demands. This table also shows the advantage of using STH, especially for small size instances. The computation time is very short, but the solution obtained is much closer to the optimum. It seems to be a good trade-off between standard MIP solvers and dispatching rules.

The gap between BDH and optimal solutions is caused by two factors. One of them is the fact that the optimal waiting time may be close to 0. In this case, even if the waiting time given by BDH is small in absolute terms, the gap can be very large in relative terms. Another factor comes from the decomposition of the problem into train-related subproblems. When solving each of such subproblems, the demands which need to be transported during few number of stations (with small values of 𝑎 𝑗 -𝑑 𝑗 ) are selected since this will maximize the number of demands transported. As a consequence, the demands which need to be transported along a large number of stations have to wait for a long time, which leads to a large total waiting time for the global problem. We are continuing working on this point for fix it.

To evaluate the limits of the MIP model, instances with up to 150 demands (all other parameters are the same) are tested, with a limit of 30 minutes on the computation time.

Table 3 summarizes the computational results for these instances. Column 1 shows the number of demands. Column "#Inf." gives the number of instances without any feasible solution, due to the impossibility of transporting all demands for instance. Column "#Solved" shows the number of instances solved to optimality by CPLEX within 30 minutes and Column "C.T. MIP" gives the average computation times for those instances and column "Gap (Cplex)" gives the average optimality gap in percentage for the instances which are feasible but failed to be solved to optimality within 30 minutes. Column "#Inc." shows the number of instances where some demands are unloaded in the solution provided by STH. Such a solution is referred to as incomplete in the remainder. Column "C.T. STH" gives the average computation times of STH. Finally, the last column gives the mean gap measured in relative terms between the solution provided by STH (considering only instances for which all demands are loaded) and the best solution given by MIP within 30 minutes.

On the one hand, the computational results reported in Table 3 show that with 150 demands, the MIP model is not able to solve all instances to optimality. On the other hand, we observe that STH gives solutions very quickly (within less than a second), with a gap of around 40%. However, it is not able to find a complete solution to most instances with all demands loaded while such solutions exist, particularly for instances with 150 demands. To evaluate the computational limits of STH, we have tested additional instances with more demands to be transported. For almost all instances, the yielded solutions are incomplete. Note that the computation times do not exceed 5 seconds even for instances with 1,000 demands. An analysis of these results shows that the two constraints on train capacity and waiting time in stations lead to very few possibilities of loading demands into each train, which explains the ability of STH to provide solutions very quickly, even with a large number of demands.

To confirm these conclusions, we have increased the train capacity to 100 boxes and reduced the time required to lead one box to 1 second, even though such values are unrealistic. The test on 25 instances with 1,000 demands shows a relative slight increase in computation times. A solution is nevertheless obtained in less than 7 minutes on average. We further evaluate the impact of the algorithms on the different core components of the railway system. Hence, this impact is studied regarding the dynamics of the demands, the use of trains and stations. Thus, we propose several performance measures to highlight the behavior of each algorithm.

Impact on transported demands:

To characterize the goods waiting time, the average waiting times of the demands at stations are computed and reported in the column "Mean" of Table 4. However, it is also important to have a certain balance of performance between the stations of the line. Thus, it is suggested to compute the average waiting times for the first three stations, the three middle stations and the last three ones as shown in Figure 5 (noted respectively, MS, MM and ME in Table 4).

The optimization of the total waiting time generates solutions with imbalanced waiting times in stations. Indeed, the waiting time at each station increases during the trip. This phenomenon could be explained partly by the fact that the train is empty at the beginning and is gradually filled up as it moves to the end of the line. Moreover, at the first stations there are generally no unloading operations whereas in the middle of the line, both loading and unloading operations are necessary and the limit on waiting time therefore quickly runs out, which limits the number of boxes to load and unload. Balancing waiting time in stations makes the total waiting time longer. In practice, the majority of demands depart at the first stations of the line. It is interesting to note the ability of the BDH and STH to reproduce the same behavior than the MIP model. The analysis of detailed results in Table 4 shows that the waiting time of demands increases sharply when the index of station increases and the waiting times increase in all stations with the number of demands.

An interesting feature of the MIP model is its ability to quickly identify infeasible instances mainly due to the impossibility of transporting all demands. In practice, decision makers could expand the temporal horizon in order to artificially increase the capacity by considering next trains for loading the surplus demand.

For the 250 solved instances, the MIP model gives optimal solutions, which means that all instances are feasible. Heuristic BDH fails to find a feasible solution for only one instance, furthermore with only one non-transported demand, due to the lack of space inside the train or because of the limit on the waiting time (hence loading time) at stations.

Impact on trains:

The train efficiency is evaluated through their capacity-use rate. This rate is relative to each train and is obtained by dividing the number of boxes effectively transported by the maximum-possible number of boxes within a train noted as "𝑈𝐵 𝑡 ". To determine 𝑈𝐵 𝑡 , an idealized case in which we can best use the train capacity is considered where all demands (each composed of one box) have to be transported from one station to the next station starting from the first station of the line. This case occurs when all boxes are available at the train arrival; in other words, they can be assumed to be available at time 0. In order for 𝑈𝐵 𝑡 not to be far from reality, both temporal loading/unloading constraint and space constraint are taken into account. The formula (30) determines the value of the maximal number of boxes that could be transported as follows:

𝑈𝐵 𝑡 = 𝑚𝑖𝑛 (𝑐𝑎𝑝 𝑡 , 𝑊𝑎𝑖𝑡 𝑚𝑎𝑥 / ℎ) × 𝑆 2 ⁄ (30)

Figure 6 gives an illustration of 𝑈𝐵 𝑡 calculation regarding the previously defined parameters. The average trains' capacity-use rate is 33% for instances with 100 demands. However, as it is said previously, some demands cannot be transported, due to demands' ready-for-departure times at their departure station. Actually, some demands' ready-fordeparture times are close to the end of the operating period while the remaining space in the trains is not sufficient. For all 25 Instances with a same number of demands One way to resorb the congestion at the end of the line is to balance the loading of boxes by smoothing their arrival times at departure stations. As said in section 4, this issue could be addressed within problem 8 of Figure 3.

The minimum waiting time of trains at stations to board passengers is fixed to 𝑊𝑎𝑖𝑡 𝑚𝑖𝑛 = 30 seconds. Due to loading operations, the average waiting time increases to 37 seconds (for instances with 100 demands). Also, the average time needed for trains to run through the line from the first station to the last one varies from 49.5 minutes to 50.5 minutes, corresponding to cases with no and many (100) demands, respectively. Thus, the simulation shows that the impact of transporting goods using passenger trains on travel time is very limited with only a 2% increase.

Impact on stations:

Table 5 reports for each solution method the observed average/maximum number of demands in stations, simultaneously waiting to be transported. Moreover, the second column shows the observed average/maximum number of boxes in stations, simultaneously waiting to be picked up or to be loaded into a train. This number increases as the number of demands increases in accordance with the MIP model results. However, the boxes remain together generally for a few seconds, 5 minutes in some cases.

There is an interesting finding about the limits on the storage space. These results allow to study the boxes' dynamic flow throughout the line. An analysis of the simulation results could be used to determine the required storage space for a given set of demands. In addition, there is a correlation between the use of space in stations and parameters such as the total number of demands, the longest waiting time of trains in stations, the capacity of trains and the time needed to load/unload a box. This also shows the interest of using MIP to obtain an optimal solution, since it can lead to an up to 25% reduction in storage space. This paper addresses an environment-friendly urban freight transportation alternative using the passenger rail infrastructure. This alternative seems to represent an important potential that still needs to be evaluated, especially from technical and financial perspectives. This idea is drawing growing attention in Europe regarding the number of case studies highlighting the ecological and socio-economic benefits. Based on the case of Paris rail network, we propose a general framework to model and simulate such systems and develop some optimization methods to solve an important problem which is the basis to address the global issue.

More specifically we identify relevant issues that need to be addressed with optimization methods. Then we investigate the FRTSP which considers the most general case in resource sharing (train, rail and stations) and constitutes the basis to further address other related issues. This problem is mathematically formulated into a MIP and its computational complexity is analyzed. We propose two heuristics to obtain near-optimal solutions. The impact of these methods on different parts of the infrastructure and the dynamic behavior are evaluated using a simulation framework. A discrete-event simulation model is developed using ARENA Software. This model improves the understanding of the system's dynamics, which helps better analyze the solution. It allows to study the impact of the decisions on various core components of the transportation system.

The proposed decision-making process is a necessary step in order to evaluate the benefit for transportation companies of offering such services. It is relevant and necessary to anticipate the needs in different resources especially during network extension as it is the case of the "Grand Paris" project. Furthermore, the approach combining optimization with simulation proposed in this paper could also be used to help decision-makers to gradually schedule customer demands by finding the best loading time considering an existing load. In addition, the simulation model could be also used to take into account disturbances in operations such as train delays or incidents on the network.

Due to the simulation results, we identify some drawbacks of BDH and STH due to the decomposition into singletrain-related subproblems. The next step consists of addressing the links between the trains. Another interesting direction is the generalization of the FRTSP to the multi-line problem where transshipment could be possible via transition hubs. This extension can improve the coverage rate but needs more handling operations in transition hubs. Another promising and relevant extension to get a better coverage rate is incorporating multimodal transportation by considering other transportation modes such as bus or self-service electric cars.

Figure 1 :

 1 Figure 1: An illustration of freight transport using Paris passenger rail network.

Figure 2 :

 2 Figure 2: The temporal hierarchical schema decomposing the global issue into 9 sub-problems.

Figure 3 :

 3 Figure 3: An illustration of trains and demand queues in the FRTSP.

  objective problem can be solved by solving successively two single-objective problems P1 and P2 defined as follows.

Figure 4 :

 4 Figure 4: The ARENA Model.

Figure 5 :

 5 Figure 5: Waiting times measures for the railway line.

Figure 6 :

 6 Figure 6: An illustration of 𝑈𝐵 𝑡 calculation based on the case study.

  Table 1 summarizes the notation used throughout the paper.

	Table 1 Notation. Indexes j : 1, …, J t : 1, …, T s : 1, …, S And Parameters 𝑟 𝑗 𝑑 𝑗 𝑎 𝑗 𝑙 𝑡 J T S 𝐶 𝑠 𝑡𝑡 𝑠 𝐽 𝑠 𝐽 𝑠 ′ 𝐷 𝑗 𝑄 𝑗 𝑐𝑎𝑝 𝑡 𝑊𝑎𝑖𝑡 𝑚𝑎𝑥 𝑊𝑎𝑖𝑡 𝑚𝑖𝑛 ℎ M Decision Variables 𝑥 𝑗,𝑡,𝑠 𝑦 𝑖,𝑗 ) Station 1 Demands Queue j=7 ( 1) j=9 ( j=1 ( 2) 1 if 𝑖 ∈ 𝐷 s=1 for demands for trains for stations ready-for-departure time for demand j departure station for demand j arrival station for demand j train t's departure time from the station 1 number of demands number of trains number of stations Storage capacity at station s travel time from station s to the next one set of demands needing to pass by station 𝑠 set of demands departing from or arriving at station s set of demands departing from the same station as demand 𝑗 and is ready for departure earlier than 𝑗: 𝐷 𝑗 = {𝑖 < 𝑗|𝑑 𝑖 = 𝑑 𝑗 } number of boxes required to pack demand j goods transport capacity of train t maximum waiting time of trains at any station minimum waiting time of trains at any station time needed for handling (loading/unloading) a single box A large positive number 1 if demand j is in train t at station s, 0 otherwise s=2 s=4 S-1 Station 4 Demands Queue j=3 ( 5) j=5 ( 3) j=8 ( 2) j=10 ( 2)	S

𝑗 and i is not yet loaded when j becomes ready for departure 𝐶 𝑡,𝑠 waiting time of train t at station s 𝑅 𝑗 time at which demand j is loaded (at station 𝑑 𝑗 )

  ∑ (𝑅 𝑗 -𝑟 𝑗 𝑥 𝑗,𝑑 𝑗 )

			𝑗∈𝛺 𝑡		(17)
	subject to
	𝑥 𝑗,𝑑 𝑗 ≤ 1, 𝑗 ∈ Ω 𝑡		(18)
	𝑥 𝑗,𝑠 -𝑥 𝑗,𝑠+1 = 0 𝑠 ∈ [𝑑 𝑗 , 𝑎 𝑗 -1], 𝑗 ∈ Ω 𝑡	(19)
	∑ 𝑗∈𝐽 𝑠	𝑥 𝑗,𝑠	× 𝑄 𝑗 ≤ 𝑐𝑎𝑝 𝑡 𝑠 = 1, 2, … , 𝑆	(20)
	𝑥 𝑗,𝑑 𝑗 × 𝑟 𝑗 ≤ 𝑙 𝑡 + ∑ 𝑑 𝑗 -1 (𝐶 𝑠 ′ + 𝑡𝑡 𝑠 ′ ) 𝑠 ′ =1	𝑗 ∈ Ω 𝑡	(21)

Table 2

 2 Computational results of MIP, Best-Dispatching-Rule Heuristic and Single-Train-based Heuristic.For the MIP model, this table gives the numbers of variables and constraints, the mean computation time, and the mean waiting time. It reports for the heuristics BDH and STH, the mean waiting time and the mean gap versus the optimal solution measured in relative terms.

	Number of	Number of	Number of	C.T. MIP	W.T.	Gap	Gap	C.T. STH
	demands	Variables	Constraints	(CPU sec.)	MIP	(BDH vs MIP)	(STH vs MIP)	(CPU sec.)
	10	3 600	4 510	0.1	251	56.22%	0.04%	~0
	20	6 900	7 820	0.2	316	28.32%	1.11%	~0
	30	10 200	11 130	0.4	365	26.56%	3.60%	~0
	40	13 500	14 400	0.5	401	23.48%	4.55%	~0
	50	16 800	17 750	0.6	421	23.89%	9.45%	~0
	60	20 100	21 060	1.0	470	29.26%	13.06%	~0
	70	23 400	24 370	1.5	491	30.29%	17.53%	0.1
	80	26 700	27 680	3.0	574	43.36%	24.66%	0.1
	90	30 000	30 990	3.5	577	40.76%	27.41%	0.1
	100	33 300	34 300	14.9	704	36.71%	31.29%	0.1

Table 3

 3 Computational results of MIP and Single-Train-based Heuristic for instances with 110 to 150 demands

			MIP results		STH results	Gap STH
	𝐽	#Inf.	#Solved	C.T. MIP (CPU sec.)	Gap (Cplex)	#Inc.	C.T. STH (CPU sec.)	vs MIP (best sol.)
	110	0	25	43	-	1	0.34	41.87
	120	0	25	265	-	1	0.38	44.06
	130	0	24	395	2.22	7	0.41	37.57
	140	2	12	732	1.54	12	0.47	41.43
	150	3	0	-	6.52	20	0.82	45.07

Table 4

 4 Simulation results on average waiting times (in seconds).

	Demand		MIP			BDH			STH
	Sizes	Mean	MS	MM	ME	Mean	MS	MM	ME	Mean	MS	MM	ME
	10	172	186	139	191 253	204	247	308	172	186	139	191
	20	303	302	264	343 369	314	306	486	306	305	267	347
	30	352	318	310	430 450	307	412	632	365	329	321	445
	40	402	353	333	522 488	336	378	749	420	369	348	546
	50	409	327	334	565 521	336	413	813	448	358	366	618
	60	466	363	391	644 605	345	468 1003 527	410	442	728
	70	495	390	409	685 641	365	490 1069 582	458	481	805
	80	564	447	481	763 830	394	531 1564 703	557	600	951
	90	571	452	529	733 818	393	597 1464 727	576	674	934
	100	678	474	631	928 939	374	630 1813 890	622	828 1218

Table 5

 5 Simulation results about stations use.

	Number	MIP	BDH	STH
	of	Avg/Max	Avg/Max	Avg/Max	Avg/Max	Avg/Max	Avg/Max
	demands	Dem.	Box.	Dem.	Box.	Dem.	Box.

ACKNOWLEDGMENTS

The authors would like to express their gratitude to Prof. Jiuh-Biing Sheu (Editor-in-Chief) and the anonymous reviewers for their constructive remarks and which have significantly helped improve this paper.