Make penance cost for accommodation/services consistent

[charvolant]

Accomodation is "I would walk x km to avoid this" services are "I would walk x km to get this" In both cases, make more = good.

[charvolant]

Making this consistent would help with user confusion but this is kind of difficult. There are several underlying problems.

• Penance is essentially additive
• You have to choose one and one only accommodation option each night and the preferences rank the relative desires for these. This is in contrast to the services which accumulate.
• The scale where worst = 0km and best = ?km is kind of messy conceptually but can be made to work
• Looking ahead to see if there is something coming up is nigh impossible in the first stage of dynamic programming and the second stage has it baked in.

Possible solutions

• Simply make the penance cost negative. That way, high values reduce the penance for travelling a longer distance.
• Make the actual penance cost max(penance) - penance. This still makes the penance cost positive but may result in "what?" reactions from people looking at the breakdown.
• Treat a location with a particular type of accomodation as "zero" with a budget beyond that increasing cost up to the point where you go beyond that accomodation type's distance. Example:

Accomodation	Penance
MunicipalAlbergue	5.0km
PrivateAlbergue	4.0 km
GuestHouse	3.0 km
Hotel	1.0km

Location	Accomodation	Forward Penance	Penance	Distance	Distance - Accomodation	Leg
1	PrivateAlbergue	1=4.0km	0km	0km	-4.0km	1.5km -> 2
2	Hotel	1=2.5km, 2=1.0km	2.5km	1.5km	0.5km	0.5km -> 3
3	GuestHouse	1=2.0km, 2=0.5km, 3=3.0km	0km	2.0km	-1.0km	1.5km -> 4
4	Hotel	1=0.5km, 3=1.5km, 4=1.0km	1.5km	3.5km	2.5km	1.0km -> 5
5			3=0.5km	--	4.5km	--	1.0km -> 6
6	MunicipalAlbergue, PrivateAlbergue	6=5.0km	0km	5.5km	0.5km	3.0 -> 7
7	PrivateAlbergue	6=2.0km, 7=4.0km	0km	8.5km	4.5km	1.0 -> 8
8	Hotel	6=1.0km, 7=3.0km, 8=1.0km	3.0km	9.5km	8.5km	1.0 -> 9
9	Hotel	7=2.0km, 9=1.0km	2.0km	10.5km	9.5km	--

Does this look like it makes sense? Columns 5 and 6 show the effect of negative penance. In choosing between 1 and 3, there's 1km of penance difference between types and 2km distance between the locations, so the guest house looks right. Similarly 4 and 5 have penalties that favour the guest house. 6 and 7 look equally favoured and then the hotels loose out to the private albergue at 7.

The interesting case is the difference between locations 6 and 7. Total penance using the negative penance model is 0.5km and 4.5km. The total penance using the staged process is 5.5km and 8.5km, since at 6 and 7 there's a "there's some perfectly good accomodation here within range" which overrides the tail effect of the municipal albergue.

[charvolant]

This does require looking into the future. The penance values mean "is there something better a little way down the track?" Therefore traverse the graph backwards, building a set of pre-chosen accommodation and penances. Using the above example.

Location	Accomodation	Future	Penance	Leg
1	PrivateAlbergue	3=1.0km	0km	1.5km -> 2
2	Hotel	6=1.0km, 3=2.5km	2.5km	0.5km -> 3
3	GuestHouse	6=1.5km	0km	1.5km -> 4
4	Hotel	6=3.0km	3.0km	1.0km -> 5
5		6=4.0km	--	1.0km -> 6
6	MunicipalAlbergue, PrivateAlbergue	7=1.0km	0km	3.0km -> 7
7	PrivateAlbergue		0km	1.0km -> 8
8	Hotel		0km	1.0km -> 9
9	Hotel		0km	--

The issue here is that there's no real pressure to stop at the private albergue at 7, rather than press on to the nice hotel. However, this happens globally, so it assumes that there isn't another albergue at a future location 10. Since most endpoints will have good accommodation options, this shouldn't be an issue.

[charvolant]

Fixed by adding both forward and backward nearby accommodation options