159 lines
6.3 KiB
Plaintext
159 lines
6.3 KiB
Plaintext
{
|
||
"cells": [
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"# Mobility and Smart Cities\n",
|
||
"\n",
|
||
"## GILA - Greedy Incremental Louage’s Algorithm\n",
|
||
"\n",
|
||
"### Presentation\n",
|
||
"\n",
|
||
"Louage is a transportation system in Tunisia to overcome the lack of public transportation. This system is spread across all the Tunisian territory and is used by a lot of people. In this system their are two types of trips : regional and cross-regional.\n",
|
||
"\n",
|
||
"This transportation system is very cheap and have a very high occupation level (97%). \n",
|
||
"\n",
|
||
"Drivers propose their itineraries and stops with a time window of departure and arrival and a price per seat. \n",
|
||
"\n",
|
||
"Passengers can ask to book a trip from a location to a destination with a desire departure and an arrival time window.\n",
|
||
"\n",
|
||
"Operators assigned passengers to a trip if the trip is compatible with their time window and if there is enough seats available. First come first served (FIFO). \n",
|
||
"\n",
|
||
"Other criteria could also be used like pricing, number of stops, number of changes require to achieve the trip etc. \n",
|
||
"\n",
|
||
"### Problem\n",
|
||
"\n",
|
||
"The Louage probleme is a multi-constraints and multi-objectives problem.\n",
|
||
"\n",
|
||
"Objectives :\n",
|
||
"- Maximize the number of passengers per vehicle (High occupation rate) to maximize the profit of the driver\n",
|
||
"- Maximize the number of satisfied requests (e.g. maximize the number of clients)\n",
|
||
"- Respect first in first out (FIFO) rule\n",
|
||
"- Minimize the waiting time of the passengers\n",
|
||
"- Minimize the overall sum of running itineraries duration\n",
|
||
"- As soon as a louage is full, it should leave\n",
|
||
"\n",
|
||
"Constraints :\n",
|
||
"- Coherence of time windows and travel time with normalization\n",
|
||
"- Louage’ s lines constraints\n",
|
||
"- Itinerary constraints\n",
|
||
"- Stop position depencies respected between request and organization (set of journeys)\n",
|
||
"- Respect the order of status and conditions on state transition for each journey\n",
|
||
"- Capacity of the vehicle\n",
|
||
"- Price\n",
|
||
"\n",
|
||
"How can we assigned travelers to their corresponding while respecting the constraints and maximizing the objectives ?\n",
|
||
"\n",
|
||
"### Conception\n",
|
||
"\n",
|
||
"To solve this problem the GILA algorithm uses a greedy approach. We makes the best decision at each step to reach a local optimum.\n",
|
||
"\n",
|
||
"#### Inputs\n",
|
||
"\n",
|
||
"We have two types of input in different lists : demands and offers.\n",
|
||
"\n",
|
||
"##### Demands\n",
|
||
"\n",
|
||
"Each client create a demand with the following information :\n",
|
||
"- Itinerary / Path (origin, destination)\n",
|
||
" - Contains all the stops of the itinerary\n",
|
||
" - Time window of departure (hd_minus, hd_plus)\n",
|
||
" - Time window of arrival (ha_minus, ha_plus)\n",
|
||
"- Booked placed (NP)\n",
|
||
"- Bill\n",
|
||
"- State (initialized, validated, paired, contractualized, running, realized, non realized and archived), this is used to keep track of the state of the demand during the algorithm.\n",
|
||
"\n",
|
||
"##### Offers\n",
|
||
"\n",
|
||
"Each driver realized a trip with the following information :\n",
|
||
"- Itinerary / Path (origin, destination)\n",
|
||
" - Contains all the stops of the itinerary\n",
|
||
" - Time window of departure (hd_minus, hd_plus)\n",
|
||
" - Time window of arrivals (ha_minus, ha_plus)\n",
|
||
"- Number of available seats (PlacesL)\n",
|
||
"- The driver\n",
|
||
"- The vehicle\n",
|
||
"- Status\n",
|
||
"\n",
|
||
"#### Output\n",
|
||
"\n",
|
||
"As a result, the algorithm returns an organization of journeys composed of associated the demands and offers.\n",
|
||
"Each journey is composed of :\n",
|
||
"- an itinerary\n",
|
||
"- an offer\n",
|
||
"- a list of demands\n",
|
||
"- a state\n",
|
||
"- a maximal number of seats occupied by passengers at any step of the itinerary\n",
|
||
"- the number of available seats at any step of the itinerary \n",
|
||
"\n",
|
||
"#### Normalization\n",
|
||
"\n",
|
||
"When clients are affected to a trip, their time window of departure and arrival are updated to take into account the traveling time and the time window of departure and arrival of the louage.\n",
|
||
"\n",
|
||
"We have an offer leaving between 8h and 8h30 for a trip that takes 30min and arriving between 8h to 9h30.\n",
|
||
"\n",
|
||
"Normalization will shift the arrival time window of the offer to 8h30 and 9h30.\n",
|
||
"\n",
|
||
"Trips must also be coherent:\n",
|
||
"- each status of journey must be in the defined order\n",
|
||
"- it's impossible to drop someone before picking him up so pickup location have to be before dropoff location in the itinerary \n",
|
||
"\n",
|
||
"### Examples\n",
|
||
"\n",
|
||
"#### Status\n",
|
||
"\n",
|
||
"\n",
|
||
"\n",
|
||
"#### Pairing \n",
|
||
"\n",
|
||
"\n",
|
||
"\n",
|
||
"#### Normalization\n",
|
||
"\n",
|
||
"\n"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"### Implementation"
|
||
]
|
||
},
|
||
{
|
||
"cell_type": "markdown",
|
||
"metadata": {},
|
||
"source": [
|
||
"#### Analysis\n",
|
||
"\n",
|
||
"This solution allows to solve the problem in a reasonable time even it does not reach a perfect solution all the time.\n",
|
||
"\n",
|
||
"This algorithm can also not fit real life situations. For instance, if a vehicle has 6 passengers seat, that does not mean that you can transport only 6 persons. More person could be fitted inside regardless of the number of seats and regulations."
|
||
]
|
||
}
|
||
],
|
||
"metadata": {
|
||
"kernelspec": {
|
||
"display_name": "Python 3",
|
||
"language": "python",
|
||
"name": "python3"
|
||
},
|
||
"language_info": {
|
||
"codemirror_mode": {
|
||
"name": "ipython",
|
||
"version": 3
|
||
},
|
||
"file_extension": ".py",
|
||
"mimetype": "text/x-python",
|
||
"name": "python",
|
||
"nbconvert_exporter": "python",
|
||
"pygments_lexer": "ipython3",
|
||
"version": "3.10.12"
|
||
},
|
||
"orig_nbformat": 4
|
||
},
|
||
"nbformat": 4,
|
||
"nbformat_minor": 2
|
||
}
|