Internetowy kiosk czy hipermarket?

Kupując w hipermarkecie rzadko ograniczamy się do pojedynczych produktów, bowiem hipermarket z reguły wiąże się z: dojazdem, długą drogą do półek oraz częstymi kolejkami przy kasach. Jeszcze drastyczniej widać to na przykładzie sklepów internetowych, gdzie dochodzą zazwyczaj: kilkudniowe oczekiwanie na dostawę towaru oraz dodatkowe koszty przesyłki. Jednak w przypadku większych zakupów te koszty często z nawiązką rekompensują niższe ceny towarów i znacznie większy ich wybór.

W przypadku sklepów internetowych w dążeniu do ułatwienia klientom działają tzw. „wyszukiwarki cenowe”, których zadaniem jest wyszukanie sklepu internetowego oferującego dany towar najtaniej. Pierwsza, z której korzystałem kilka lat temu była programem dla Windows i nazywała się COPERNICUS. Zwyciężyły jednak specjalne witryny umożliwiające wyszukiwanie najtańszego wskazanego produktu, takie jak: www.ceneo.pl, www.skapiec.pl i wiele innych zagranicznych.

Wada współczesnych porównywarek

Pomimo, że zakupy w sklepach internetowych mają sens głównie dla bogatszych koszyków towarów, wszystkie dotąd znane witryny tego typu pozwalają wykonywać operację minimalizacji ceny jedynie na jednym towarze naraz. Próba użycia tej funkcji do minimalizacji kosztu całego zakupu zawiedzie, bowiem z matematycznego punktu widzenia nie jest wszystko jedno czy będziemy minimalizować sumę kosztów zakupów towarów czy znajdować sumę minimalnych kosztów.

Sprawdźmy to na przykładzie, korzystania z nowej koncepcyjnie wyszukiwarki cenowej, gdzie podobnie jak w zwykłych sklepach internetowych można z katalogu wybierać towary i wstawiać je do koszyka. Zamiast podawanej zwykle konkretnej ceny zakupu towaru wprowadzono tu informowanie o liczbie sklepów, w jakich towar jest dostępny oraz jaką ma najniższą, a jaką najwyższą cenę.:

Tylko najtaniej

Sumując najniższe ceny towarów uzyskamy kwotę: 325 zł, ale tu czeka nas zimny prysznic, bowiem musimy doliczyć koszty dostawy, co w tym przypadku, gdy będziemy kupować aż w dziewięciu sklepach, jak nam sugeruje minimalizacja kosztu zakupu każdego towaru oddzielnie: INTAK, SKLEP09, SKLEP11, SKLEP12, SKLEP13, SKLEP14, SKLEP15, SKLEP20, SKLEP21 wyniesie: 151zł. Razem da to, więc kwotę zakupu: 476zł, co okazuje się zupełnie bez sensu, bo kupując wszystko w jakimś jednym sklepie możemy tak dobrze zaoszczędzić na kosztach dostawy, że zrekompensuje to wyższe ceny.

A najlepiej

Jednak jak to już częściowo widać na poprzednim ekranie można podzielić zakup na dwa sklepy i jeśli zrobimy to w sposób przemyślany to możemy uzyskać znacznie lepszy rezultat.

Optymalnie

Problem znajdowania optymalnego sposobu podziału koszyka na zakupy w różnych sklepach internetowych jest niebanalny, dlatego że jeśli mamy n sklepów i k towarów w koszyku to z faktu, że można każdy towar w koszyku przydzielić do dowolnego sklepu wynika, że przestrzeń poszukiwań wynosi kⁿ. Zmienna w wykładniku to „bomba” obliczeniowa, która „wybucha” już po przekroczeniu wartości kilkadziesiąt dla n i k powodując tzw. „eksplozję obliczeniową”. Niekiedy jednak pomimo potencjalnie olbrzymich przestrzeni udaje się skonstruować sprawne algorytmy.

W tym przypadku można przeszukiwać przestrzeń zbiorów sklepów zaniedbując towary w koszyku, bowiem jeśli mamy ustalony zbiór sklepów, w których na pewno kupujemy to koszt dostawy jest sumą kosztów dostawy w tych sklepach, a koszt koszyka towarów to suma minimalnych kosztów poszczególnych towarów po ustalonych do użycia sklepach. Warto jako ćwiczenie napisać funkcje obliczające te koszty prze założeniu, że w tablicy dwuwymiarowej mamy zgromadzone ceny produktów na przecięciu rodzaju produktu z numerem sklepu. Wiersz 0 tablicy może zawierać koszty dostawy dla poszczególnych sklepów.

Idea algorytmu

Zauważmy, że rozdział zakupów na dużą liczbę sklepów będzie raczej rzadki, bowiem tylko zakup bardzo drogich towarów może zrekompensować niemałe przecież koszty dostawy nad niewielkimi procentowo różnicami cen w sklepach internetowych. Warto, więc zacząć poszukiwania od pojedynczych sklepów i stopniowo powiększać ich liczbę tak by można przerwać obliczenia po upływie przeznaczonego na to czasu z niewielkim prawdopodobieństwem pominięcia ciekawych rozwiązań.

Najwygodniej będzie zacząć od pustego zbioru sklepów wstawionego na początek listy. Dalej począwszy od początku listy następuje jej przetwarzanie element po elemencie aż dojdziemy do końca listy. Nie nastąpi to jednak szybko, bo lista będzie się stale powiększała. Otóż każdy przeglądany zbiór sklepów jest powiększany o kolejny sklep spośród wszystkich niewykorzystanych w tym łańcuchu, a więc większych niż największy numer sklepu już umieszczonego w zbiorze.

Dla prezentacji algorytmu wykorzystamy notację języka PHP, w którym ten algorytm działa w witrynie www.taniszyk.pl. Najbardziej charakterystyczną cechą języka jest chyba wyróżnianie zmiennych znakiem dolara na początku, co jest znane z takich języków programowania jak LISP(lata 60-te) czy PROLOG(lata 70-te). Poza tym jest wiele podobieństw do C i C++ np. ”wąsate” nawiasy instrukcji czy budowa „for”. Wynikiem działania tego algorytmu są wartości zmiennych: $aktualnemin, $sklepymin oraz cała lista $wezel pozwalająca użytkownikowi znaleźć odpowiednie dla niego rozwiązanie. Natomiast jako dane wejściowe występują: $lsklepów, $deadline oraz używane jedynie wewnątrz funkcji kosztdostawy i kosztkoszyka zmienne opisujące zawartość koszyka i ceny zakupu poszczególnych towarów/ceny dostaw w zależności od sklepu.

ALGORYTM MINIMALIZACJI KOSZTÓW ZAKUPU TOWARÓW W SKLEPACH INTERNETOWYCH

$wezel=array();   //$wezel zapamiętuje możliwe kombinacje sklepów
$wezel[] = array(); //zaczynamy od pustego zbioru sklepów
reset($wezel);//ustawiamy wskaźnik na początek tablicy
$sklepy=current($wezel);//inicjujemy $sklepy pierwszym zbiorem pustym
do{
if(count($sklepy)==0)$is=1;else$is=max($sklepy)+1;//starannie dobieramy numer kolejnego sklepu by zbiory się nie powtarzały
for($s=$is;$s<=$lsklepow;$s++){
if (time()>$deadline) return;//pozwala przerwać poszukiwania w sensowym czasie
$wiecejsklepow=$sklepy;
$wiecejsklepow[]=$s;//powiększamy zbiór sklepów o kolejny
$wezel[]=$wiecejsklepow;//wstawiamy zbiór sklepów na listę
$koszt = kosztdostawy($wiecejsklepow)+ kosztkoszyka($wiecejsklepow);
if($koszt<$aktualnemin){//jeśli to najlepsze wśród dotąd poznanych
$aktualnemin = $koszt;
$sklepymin = $wiecejsklepow;
}
}
next($wezel);//przesuwamy na kolejny zbiór sklepów
}while($sklepy=current($wezel));//i pobieramy kolejny zbiór sklepów do przetwarzania

Algorytm ten jako jądro serwisu sprawuje się zaskakująco dobrze rzadko powodując skrócenie poszukiwań pod wpływem ograniczeń czasowych.

Chciałbym w tym miejscu podziękować dr inż. Adamowi Wojciechowskiemu za podzielenie się pomysłem optymalizacji całego koszyka zakupów oraz naszym byłym magistrantom Michałowi Kabzińskiemu i Adrianowi Lorenzowi, których pomoc we wdrażaniu tego pomysłu była dla autora tej pracy niezwykle inspirująca.