2
$\begingroup$

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.

EDIT:: Read me file:

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – ooo
    Apr 3, 2020 at 16:29

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.