# Montoya et al. 2017 benchmark Results

I am testing Montoya et al. 2017 dataset and trying to replicate the Result from this paper The electric vehicle routing problem with capacitated charging stations. I am unable to replicate the exact Result.

Montoya et al. 2016
Instances for the electric vehicle routing problemw with non-linear charging functions
Number of instances: 120
-------------------------------------------------------------------------------------------------------------
<network>
- the node with type=0 is the depot
- the nodes with type=1 are the customers
- the nodes with type=2 are the charging stations (CSs)
- coordinates are given in km
- nodes with type=2 define the type of charging station (slow, normal, fast) in tag <cs_type>
- computations must be done using double precision (14 decimal) Euclidean distances
<fleet>
- There is just one type of electric vehicle in the 120 instances
- Routes start and end at node 0 (the depot)
- <speed_factor> is given in km/h
- <consumption_rate> defines the energy consumption in wh/km
- <battery_capacity> defines the total capacity in wh
- <function cs_type="X"> defines the charging function of the electric vehicle when charged at a station of type X
- The charging functions are piecewise linear functions with 3 break points (pus point 0,0)
- The break points are given in 2D coordinates (X:<charging_time>,Y:<battery_level>)
- <battery_level> is given in wh
- <charging_time> is given in h
<requests>
- Each customer has 1 request
- Each customer has a service time

Instances are named using the following convention: tcAcBsCcDE, where:
- A is the method used to place the customers (i.e., 0: random uniform, 1: clustered, 2: mixture of both)
- B is the number of customers
- C is the number of the CSs,
- D is 't' if the CSs are located using a p-median heuristic and 'f' if the CSs were randomly located
- E is the number of the instance for each combination of parameters (i.e., E={0,1,2,3,4}).


For example here - tc0c10s2ct1:

<?xml version="1.0" encoding="UTF-8"?>
<instance>
<info>
<dataset>Montoya et al. 2016</dataset>
<name>tc0c10s2ct1</name>
</info>
<network>
<nodes>
<node id="0" type="0">
<cx>77.59</cx>
<cy>78.35</cy>
</node>
<node id="1" type="1">
<cx>12.44</cx>
<cy>47.61</cy>
</node>
<node id="2" type="1">
<cx>108.2</cx>
<cy>93.64</cy>
</node>
<node id="3" type="1">
<cx>58.51</cx>
<cy>24.22</cy>
</node>
<node id="4" type="1">
<cx>116.26</cx>
<cy>13.76</cy>
</node>
<node id="5" type="1">
<cx>113.56</cx>
<cy>85.73</cy>
</node>
<node id="6" type="1">
<cx>5.09</cx>
<cy>69.91</cy>
</node>
<node id="7" type="1">
<cx>89.27</cx>
<cy>58.94</cy>
</node>
<node id="8" type="1">
<cx>78.54</cx>
<cy>57.16</cy>
</node>
<node id="9" type="1">
<cx>111.56</cx>
<cy>51.2</cy>
</node>
<node id="10" type="1">
<cx>11.05</cx>
<cy>72.52</cy>
</node>
<node id="11" type="2">
<cx>20.26</cx>
<cy>60.26</cy>
<custom>
<cs_type>fast</cs_type>
</custom>
</node>
<node id="12" type="2">
<cx>70.9</cx>
<cy>30.98</cy>
<custom>
<cs_type>fast</cs_type>
</custom>
</node>
</nodes>
<euclidean />
<decimals>14</decimals>
</network>
<fleet>
<vehicle_profile type="0">
<departure_node>0</departure_node>
<arrival_node>0</arrival_node>
<max_travel_time>10</max_travel_time>
<speed_factor>40</speed_factor>
<custom>
<consumption_rate>125</consumption_rate>
<battery_capacity>16000</battery_capacity>
<charging_functions>
<function cs_type="fast">
<breakpoint>
<battery_level>0</battery_level>
<charging_time>0.0</charging_time>
</breakpoint>
<breakpoint>
<battery_level>13600</battery_level>
<charging_time>0.31</charging_time>
</breakpoint>
<breakpoint>
<battery_level>15200</battery_level>
<charging_time>0.39</charging_time>
</breakpoint>
<breakpoint>
<battery_level>16000</battery_level>
<charging_time>0.51</charging_time>
</breakpoint>
</function>
</charging_functions>
</custom>
</vehicle_profile>
</fleet>
<requests>
<request id="1" node="1">
<service_time>0.5</service_time>
</request>
<request id="2" node="2">
<service_time>0.5</service_time>
</request>
<request id="3" node="3">
<service_time>0.5</service_time>
</request>
<request id="4" node="4">
<service_time>0.5</service_time>
</request>
<request id="5" node="5">
<service_time>0.5</service_time>
</request>
<request id="6" node="6">
<service_time>0.5</service_time>
</request>
<request id="7" node="7">
<service_time>0.5</service_time>
</request>
<request id="8" node="8">
<service_time>0.5</service_time>
</request>
<request id="9" node="9">
<service_time>0.5</service_time>
</request>
<request id="10" node="10">
<service_time>0.5</service_time>
</request>
</requests>
</instance>


My Result:

 visit   charge Left      Distance Traveled     Charge Time
0  16000.000000000000    1.000000000000  0.000000000000
7  13168.341640928415   23.653266872629  0.000000000000
8  11808.761627652219   34.529906978831  0.000000000000
11  16000.000000000000   92.892295552301  0.407119592116
10  14083.249413069105  108.226300247712  0.000000000000
6  13269.945003576588  114.732735523605  0.000000000000
1  10334.939413718195  138.212780242437  0.000000000000
3   3876.494118989694  189.880342600285  0.000000000000
12  16000.000000000000  203.994509242359  0.461853733869
4   9935.170550625542  252.513144837343  0.000000000000
12  16000.000000000000  301.031780432328  0.421778989613
9  10323.728116095881  346.441955503542  0.000000000000
5   6000.244097101502  381.029827655526  0.000000000000
2   4805.871222953778  390.584810648696  0.000000000000
0    528.831870200578  424.801125470665  0.000000000000


Total time travel + charging = 11.885 + service Time(0.5*10) = 16.885, but in paper tc0c10s2ct1 - 12.30

for another example tc0c10s2cf1:

<?xml version="1.0" encoding="UTF-8"?>
<instance>
<info>
<dataset>Montoya et al. 2016</dataset>
<name>tc0c10s2cf1</name>
</info>
<network>
<nodes>
<node id="0" type="0">
<cx>77.59</cx>
<cy>78.35</cy>
</node>
<node id="1" type="1">
<cx>12.44</cx>
<cy>47.61</cy>
</node>
<node id="2" type="1">
<cx>108.2</cx>
<cy>93.64</cy>
</node>
<node id="3" type="1">
<cx>58.51</cx>
<cy>24.22</cy>
</node>
<node id="4" type="1">
<cx>116.26</cx>
<cy>13.76</cy>
</node>
<node id="5" type="1">
<cx>113.56</cx>
<cy>85.73</cy>
</node>
<node id="6" type="1">
<cx>5.09</cx>
<cy>69.91</cy>
</node>
<node id="7" type="1">
<cx>89.27</cx>
<cy>58.94</cy>
</node>
<node id="8" type="1">
<cx>78.54</cx>
<cy>57.16</cy>
</node>
<node id="9" type="1">
<cx>111.56</cx>
<cy>51.2</cy>
</node>
<node id="10" type="1">
<cx>11.05</cx>
<cy>72.52</cy>
</node>
<node id="11" type="2">
<cx>93.39</cx>
<cy>10.8</cy>
<custom>
<cs_type>fast</cs_type>
</custom>
</node>
<node id="12" type="2">
<cx>8.9</cx>
<cy>10.98</cy>
<custom>
<cs_type>fast</cs_type>
</custom>
</node>
</nodes>
<euclidean />
<decimals>14</decimals>
</network>
<fleet>
<vehicle_profile type="0">
<departure_node>0</departure_node>
<arrival_node>0</arrival_node>
<max_travel_time>10</max_travel_time>
<speed_factor>40</speed_factor>
<custom>
<consumption_rate>125</consumption_rate>
<battery_capacity>16000</battery_capacity>
<charging_functions>
<function cs_type="fast">
<breakpoint>
<battery_level>0</battery_level>
<charging_time>0.0</charging_time>
</breakpoint>
<breakpoint>
<battery_level>13600</battery_level>
<charging_time>0.31</charging_time>
</breakpoint>
<breakpoint>
<battery_level>15200</battery_level>
<charging_time>0.39</charging_time>
</breakpoint>
<breakpoint>
<battery_level>16000</battery_level>
<charging_time>0.51</charging_time>
</breakpoint>
</function>
</charging_functions>
</custom>
</vehicle_profile>
</fleet>
<requests>
<request id="1" node="1">
<service_time>0.5</service_time>
</request>
<request id="2" node="2">
<service_time>0.5</service_time>
</request>
<request id="3" node="3">
<service_time>0.5</service_time>
</request>
<request id="4" node="4">
<service_time>0.5</service_time>
</request>
<request id="5" node="5">
<service_time>0.5</service_time>
</request>
<request id="6" node="6">
<service_time>0.5</service_time>
</request>
<request id="7" node="7">
<service_time>0.5</service_time>
</request>
<request id="8" node="8">
<service_time>0.5</service_time>
</request>
<request id="9" node="9">
<service_time>0.5</service_time>
</request>
<request id="10" node="10">
<service_time>0.5</service_time>
</request>
</requests>
</instance>


My Result:

 visit   charge Left      Distance Traveled     Charge Time
0  16000.000000000000    1.000000000000  0.000000000000
7  13168.341640928411   23.653266872629  0.000000000000
8  11808.761627652217   34.529906978831  0.000000000000
12  16000.000000000000  118.090196590638  0.478915082207
1  11399.917629813544  154.890855552163  0.000000000000
10   8281.323695842644  179.839607023983  0.000000000000
6   7468.019286350116  186.346042299876  0.000000000000
12  16000.000000000000  245.399077784969  0.508030819589
3   9581.703764821985  296.745447666384  0.000000000000
11  16000.000000000000  334.118041903363  0.398077930861
4  13117.405411352520  357.178798612556  0.000000000000
11  16000.000000000000  380.239555321750  0.276706518021
9  10462.755508152066  424.537511256523  0.000000000000
5   6139.271489157687  459.125383408507  0.000000000000
2   4944.898615009963  468.680366401677  0.000000000000
0    667.859262256759  502.896681223647  0.000000000000


Total time travel + charging = 14.209 + service Time(0.5*10) = 19.209, but in paper tc0c10s2cf1 - 19.75

What is wrong with my Result?

My objective function minimizes distance traveled and charging time. (Not using an exact formulation from the paper, I am trying a simple formulation)

for charging time I am using:

f = opt_model.piecewise(0, [(0, 0), (13600, 0.31), (15200, 0.39), (16000, 0.51)], 1)


I have used simple flow and charging constraints.

• I have noticed that even simple TSP on tc0c10s2ct1 takes times about 8-9 and on top of that 0.5*10 service time always goes greater than 12.5 that is without charging, with charging it will take more time.
– ooo
Commented Apr 3, 2020 at 16:29